Scala - 使用 DFS 检测周期?我的代码有问题,我似乎无法弄清楚为什么
Scala - Use DFS for detecting a cycle? My code is buggy, and I can't seem to figure out why
我正在尝试编写一个函数,如果图形有一个循环,该函数 returns 为真,但我正在苦苦挣扎。我在 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 惯用语(在集合、集合、不可变列表上使用查找...):
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
的答案感兴趣
我正在尝试编写一个函数,如果图形有一个循环,该函数 returns 为真,但我正在苦苦挣扎。我在 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 惯用语(在集合、集合、不可变列表上使用查找...):
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
的答案感兴趣