首页 文章

Scala - 使用DFS检测周期？我的代码是错误的，我似乎无法弄清楚为什么

提问于
浏览 次
1

我正在尝试编写一个函数，如果图形有一个循环，则返回true，但我非常挣扎 . 我在Scala中表示如下所示的图，其中每个子列表的索引表示节点0,1,2以后，并且该子列表的组件指示从子列表的索引到节点 2 的边缘，例如成本 1 . 请注意，这是一个无向图表示 . 下面是一个具有循环的无向图的示例 .

ListBuffer(
  ListBuffer((1, 1), (2, 1), (3, 1)),
  ListBuffer((0, 1), (2, 2), (3, 2)),
  ListBuffer((0, 1), (1, 2)),
  ListBuffer((0, 1), (1, 2)))
)

这是我的代码，但它不起作用，我似乎无法弄清楚为什么 .

def hasCycle(graph: ListBuffer[ListBuffer[(Int, Int)]]): Boolean = {
  var visited: HashSet[Int] = HashSet()
  var lst: ListBuffer[Int] = ListBuffer()
  for (node <- graph.indices) {
    if (visited.contains(node)) {
      true
    } else {
      visited += node
      for (item <- getChildren(graph, node)) {
        visited += item
        lst += item
      }
      for (i <- lst) {
        visit(graph, i, node)
        lst = ListBuffer()
      }
    }
  }
  def visit(g: ListBuffer[ListBuffer[(Int, Int)]], node: Int, parent: Int): Unit = {
    for (child <- getChildren(g, node)) {
      if (visited.contains(child) && (child != parent)) {
          true
      } else if (!visited.contains(child) && (child != parent)) {
        visit(g, child, child)
      }
    }
  }
  false
 }
 /* Return the adjacent nodes to parent in graph */
 def getChildren(graph:  ListBuffer[ListBuffer[(Int, Int)]], parent: Int): ListBuffer[Int] = {
    var parentToChildren: Map[Int, ListBuffer[Int]] = Map()
    var childrenOfI: ListBuffer[Int] = ListBuffer()
    for (i <- graph.indices) {
      for (j <- graph(i)) {
        childrenOfI += j._1
      }
      parentToChildren += (i -> childrenOfI)
      childrenOfI = ListBuffer()
    }
    parentToChildren(parent)
  }
scala list search graph cycle

1 回答

  • 2

    这是一种方法（诚然不经过严格测试，所以让我知道！），次优但其中包含一些Scala习语（使用find on collection，Set，immutable List ...）：

    type Graph = List[List[(Int, Int)]]

val g: Graph = List(
  List((1, 1), (2, 1)),
  ...
  )

def hasCycle(g: Graph): Boolean = {
  (0 to g.length - 1).find { source => //-- is there a cycle starting at this node?
    pathTo(source, source, (0 to source).toSet)
  }.isDefined
}

def pathTo(source: Int, destination: Int, visited: Set[Int]): Boolean = {
  //-- Is there a path from source to destination excluding visited?
  g(source).find { node => //-- find first case where
    node._1 == destination || ( //-- we've reached destination, or ...
      //-- we're allowed to continue (not yet visited), and there's a path this way
      !visited.contains(node._1) && pathTo(node._1, destination, visited + node._1))
  }.isDefined
}

    顺便说一句，如果您还没有看过它们，您可能也会对How do I check if a Graph is Acyclic的答案感兴趣

    回复于

相关问题