图遍历算法的应用

Question

我正在阅读C++ 4e中与图有关的数据结构和算法(由Adam编写)。在图宽度优先搜索的实现中，psuedo代码如下所示：

BFS():
    for all vertices u
        num(u) = 0
    edges = null
    i = 1
    while there is a vertex v such that num(v) is 0
        num(v)++
        enqueue(v)
        while queue is not empty
            v = dequeue()
            if num(u) is 0
                num(u) = i++
                enqueue(u)
                attach edge(v,u) to edges
    output edges

基本上，在图的实现中，我们已经保留了一组所有的顶点和一组边。在BFS中，该算法首先枚举该集合中未访问的每个顶点，以遍历完整的图。

我的问题是:由于我们已经将所有顶点存储在一个集合中，所以我们可以在集合中循环来操作特定的顶点，而无需使用BFS算法。为什么我们需要一个图遍历算法和什么是主要用途？

Answer 1

BFS和DFS有很多用途。

想给你一个BFS的想法：

1. 您有一个表示社交网络的图表，并希望为特定用户提供朋友建议。然后，你做一个BFS。顶点(人)越近，在朋友建议列表中的排名就越好。(如果用户数很大，那么在3的距离停止，而不是对整个图执行BFS是有意义的)。
2. 解空间搜索当解空间是无限的时，非常有用。(见游戏树)
3. 最短路径(如果边有相同的权重并且没有循环)。Dijkstra对其进行了调整，以适应可变权重(参见迪克斯特拉算法)。

Answer 2

例如，当递归遍历树时，通常会隐式使用DFS。