logo标签列表

在有向图上执行深度优先搜索和广度优先搜索

algorithmgraphdepth-first-searchbreadth-first-search
6
假设我们有这样一个图形： graph 如果你想要从0到5的路径，如果我们在这个图上执行DFS和BFS算法，将按照什么顺序访问节点（假设总是先推送最小元素）? 我很难理解算法如何处理带有环的图形，我希望有人可以概述每个算法在这样的图形上所采取的过程。
1个回答
4

处理循环的常见技术是使用一组已访问过的顶点。在将顶点推入队列/栈之前，请检查其是否已被访问过。如果已经访问过，则不执行任何操作，否则从将其添加到访问集合开始，然后继续遍历图。

从上到下堆栈。

深度优先搜索：

empty stack
visiting 0: stack: 2, 1, visited: 0
visiting 2: stack: 5, 3, 1 visited: 0, 2
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5
DONE

以类似的方式进行BFS。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接