我知道的图遍历（DFS和BFS）实现使用可变的“已访问”顶点集。如何使用只有不可变数据结构来实现它们？
我看到了这个问题。现在我想知道是否还有其他解决方案。
Scala中的图遍历
6
- Michael
2
1在您链接的问题的答案中，具体缺少什么？我们应该在这里回答什么而不是那里？这是否仅涉及BFS？如果是，这是作业吗？ - Francois G
2@huitseeker 不，这不是一份作业。对于这个问题的答案看起来有点太复杂了。我会尝试Philippe的答案，它对我来说看起来还不错。 - Michael
4个回答
8
这里有一种方法可以实现：
这个技巧就是简单地传递要访问的节点列表（相当于在命令式算法中的堆栈或队列）和已访问状态的集合。
如果你担心每个递归调用时调用栈会增长，可以使用一个额外的参数使其成为尾递归函数。
这是一种可行的方式：
def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = {
if(toVisit.isEmpty) {
Seq.empty
} else {
val next = toVisit.head
val succ = (graph(next) -- visited -- toVisit).toSeq
// DFS :
// next +: traverse(graph, succ ++ toVisit.tail, visited + next)
// BFS :
next +: traverse(graph, toVisit.tail ++ succ, visited + next)
}
}
def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
traverse(graph, Seq(initial), Set.empty)
这个技巧就是简单地传递要访问的节点列表（相当于在命令式算法中的堆栈或队列）和已访问状态的集合。
如果你担心每个递归调用时调用栈会增长，可以使用一个额外的参数使其成为尾递归函数。
@annotation.tailrec
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = {
if(toVisit.isEmpty) {
accumulator
} else {
val next = toVisit.head
val succ = (graph(next) -- visited -- toVisit).toSeq
// DFS :
//traverseTR(graph, succ ++ toVisit.tail, visited + next, accumulator :+ next)
// BFS :
traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next)
}
}
def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
traverseTR(graph, Seq(initial), Set.empty, Seq.empty)
使用此方法，您可以获得与使用while循环编写的版本一样高效的版本。
- Philippe
1
1请注意，在尾递归版本中，“visited”和“accumulator”包含相同的元素。原因是您希望同时具有以下两个特点：1）快速查找（以便“graph（next） - visited”的大小是线性的）和2）保留顺序。如果您有一个可以同时实现这两个功能的数据结构，那么您只需要使用它即可。 - Philippe
1
以下代码执行了几个有向图遍历。它仅使用不可变的数据结构，并且是尾递归的，但是代价很高：
List toVisit 可能包含许多重复项，因为它包含我们计划在未来访问的所有顶点。在最坏的情况下，我们可能会为图中几乎每条边添加一个顶点到列表中。因此，尾递归的空间复杂度为 O(|E| + |V|)。
对于稠密图，标准的非尾递归解决方案，其空间复杂度为 O(|V|)，更加高效，尽管它确实需要保存长度为 O(|V|) 的调用堆栈。
由于存储输入图本身需要 O(|V| + |E|) 的空间，上述成本可能是可以接受的。
提高上述内容的空间复杂度的一种可能方法是将 toVisit 替换为 List[Iterator[Vertex]]。由于迭代器是惰性求值的，因此这将将空间复杂度降低到 O(|V|)。
object DirectedGraphTraversals {
type Graph[Vertex] = Map[Vertex, Set[Vertex]]
def dfs[Vertex](graph: Graph[Vertex], initialVertex: Vertex) =
dfsRec(DfsNeighbours)(graph, List(initialVertex), Set(), Set(), List())
def topologicalSort[Vertex](graph: Graph[Vertex]) =
graphDfsRec(TopologicalSortNeighbours)(graph, graph.keySet, Set(), List())
def stronglyConnectedComponents[Vertex](graph: Graph[Vertex]) = {
val exitOrder = graphDfsRec(DfsNeighbours)(graph, graph.keySet, Set(), List())
val reversedGraph = reverse(graph)
exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){
case ((visitedAcc, connectedComponentsAcc), vertex) =>
val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(vertex), visitedAcc, visitedAcc, List()).toSet
(visitedAcc ++ connectedComponent, connectedComponent :: connectedComponentsAcc)
}._2.filterNot(_.isEmpty)
}
def reverse[Vertex](graph: Graph[Vertex]) = {
val reverseList = for {
(vertex, neighbours) <- graph.toList
neighbour <- neighbours
} yield (neighbour, vertex)
reverseList.groupBy(_._1).mapValues(_.map(_._2).toSet)
}
private sealed trait NeighboursFunc {
def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]):Set[Vertex]
}
private object DfsNeighbours extends NeighboursFunc {
def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) =
graph.getOrElse(vertex, Set()).filterNot(entered)
}
private object TopologicalSortNeighbours extends NeighboursFunc {
def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = {
val neighbours = graph.getOrElse(vertex, Set())
if(neighbours.exists(neighbour => entered(neighbour) && !exited(neighbour)))
throw new IllegalArgumentException("The graph is not a DAG, it contains cycles: " + graph)
else
neighbours.filterNot(entered)
}
}
@tailrec
private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[Vertex],
entered: Set[Vertex], exited: Set[Vertex],
exitStack: List[Vertex]): List[Vertex] = {
toVisit match {
case List() => exitStack
case hd :: tl =>
if(exited(hd))
dfsRec(neighboursFunc)(graph, tl, entered, exited, exitStack)
else if(entered(hd) && !exited(hd))
dfsRec(neighboursFunc)(graph, tl, entered, exited + hd, hd :: exitStack)
else { // not entered yet
dfsRec(neighboursFunc)(graph, neighboursFunc(graph, hd, entered, exited) ++: toVisit, entered + hd, exited, exitStack)
}
}
}
@tailrec
private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex],
visited: Set[Vertex], order: List[Vertex]): List[Vertex] = {
if(notVisited.isEmpty)
order
else {
val orderSuffix = dfsRec(neighboursFunc)(graph, List(notVisited.head), visited, visited, List())
graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, visited ++ orderSuffix, orderSuffix ::: order)
}
}
}
object DirectedGraphTraversalsExamples extends App {
import DirectedGraphTraversals._
val graph = Map(
"B" -> Set("D", "C"),
"A" -> Set("B", "D"),
"D" -> Set("E"),
"E" -> Set("C"))
//println(dfs(graph, "A"))
println("dfs A " + dfs(graph, "A"))
println("dfs B " + dfs(graph, "B"))
println("topologicalSort " + topologicalSort(graph))
println("dfs B " + dfs(graph, "B"))
println("reverse " + reverse(graph))
println("stronglyConnectedComponents graph " + stronglyConnectedComponents(graph))
val graph2 = graph + ("C" -> Set("D"))
println("stronglyConnectedComponents graph2 " + stronglyConnectedComponents(graph2))
println("topologicalSort graph2 " + Try(topologicalSort(graph2)))
}
- Mishael Rosenthal
0
前面的解决方案存在一些问题：
效率低下：(graph(next) -- visited -- toVisit).toSeq 可能与图的大小成线性关系。
DFS 版本不正确，因为它没有按照 DFS 的顺序进行访问： 例如，如果您有以下图形：
Map("A" -> Set("B", "D"), "B" -> Set("C", "D"), "C" -> Set(), "D" -> Set("E"), "E" -> Set())
然后，如果您从 A 开始运行 DFS，则合法的 DFS 访问顺序为：
A, B, C, D, E A, B, D, E, C A, D, E, B, C
上述算法可能以以下非法顺序访问顶点： A, D, B, C, E
因为在第一次迭代中，您将 D 和 B 都添加到 toVisit 序列中。
- Mishael Rosenthal
0
您可以像下面这样进行遍历 -
object FindPathsFromANode extends App {
val startNode = "a"
val inputNodes = List(Node("a", "x"), Node("a", "b"), Node("b", "c"), Node("c", "d"), Node("b", "y"), Node("b", "z"), Node("d", "a"))
def findPaths(allNodes: List[Node], newNode: Node, path: List[Node] = Nil, isVisited: List[String] = Nil, allPaths: List[List[Node]] = Nil): List[List[Node]] = {
if (isVisited.contains(newNode.dest)) {
allPaths ++ List(path)
} else {
val nextNodes = allNodes.filter(_.source == newNode.dest)
if (nextNodes.isEmpty) {
allPaths ++ List(path :+ newNode)
} else if (nextNodes.size > 1) {
nextNodes.flatMap { node =>
findPaths(allNodes, node, path :+ newNode, isVisited :+ newNode.source)
}
} else {
findPaths(allNodes, nextNodes.head, path :+ newNode, isVisited :+ newNode.source)
}
}
}
val startNodes = inputNodes.filter(_.source == startNode)
startNodes.flatMap(node => findPaths(inputNodes, node)).foreach(println)
}
请查看以下解决方案： https://github.com/svsachin13/GraphTraversal-scala
- Jet
1
你应该说明为什么/如何这个解决方案与多年前提交的其他解决方案不同（更好？）。 - jwvh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接