0

我正在阅读与 C++ 4e 中的数据结构和算法中的图形相关的材料（作者：Adam Drozdek）。在他的 Graph Breadth First Search 实现中，伪代码如下：

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 算法。为什么我们需要一个图遍历算法，主要用途是什么？

4

2 回答 2

2

BFS 和 DFS 有很多用途……
给你一个关于 BFS 的想法：

  1. 您有一个表示社交网络的图表，并希望为特定用户提供朋友建议。然后，您执行 BFS。顶点（人）越接近，在好友推荐列表中的排名就越高。（如果用户数量很大，在距离为 3 处停止而不对整个图进行 BFS 是有意义的）。

  2. 解空间搜索。当解决方案空间无限时非常有用。（见游戏树）

  3. 最短路径（如果边缘具有相同的权重并且没有循环）。Dijkstra 对其进行了调整以适用于可变权重（请参阅Dijkstra 算法）。

于 2014-03-27T14:45:16.897 回答
1

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

于 2014-03-27T14:49:47.497 回答