图遍历算法的用法

我正在阅读与C++ 4e中的数据结构和算法中的图相关的材料（作者：Adam Drozdek）。在他实现图形广度优先搜索中，伪代码如下：图遍历算法的用法

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算法的情况下对特定顶点进行操作。为什么我们需要一个图遍历算法，主要用途是什么？

来源

2014-03-27 Vschon

有对BFS和DFS许多用途...
为了给你一个BFS一个想法：

你有代表的社交网络图，并希望使特定用户朋友的建议。然后，你做一个BFS。顶点（人物）越接近，朋友建议列表中的等级越高。（如果用户数量很大，则在距离3处停止而不在整个图表上执行BFS是有意义的）。
解决方案空间搜索。解决方案空间无限时非常有用。（请参阅Game Trees）
最短路径（如果边具有相同的权重并且没有循环）。 Dijkstra调整它适用于可变权重（见Dijkstra's algorithm）。

来源

2014-03-27 14:45:16 Radu

所以遍历算法的目的不是主要访问一些顶点，而是探索不同顶点之间的关系，对吗？ – Vschon

可以这样说。但是，当你访问顶点时，你也可以调用一些函数。也许我想为所有顶点分配一个优先级，它们越接近，优先级越高。因此，我做了一个BFS并在每个节点访问中调用一个函数。该功能分配优先级。当你到达树时，你会看到有多个应用程序也可用于各种树遍历（预订，按序和后序）。 – Radu

现在对我来说更有意义，谢谢！ – Vschon

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

来源

2014-03-27 14:49:47 Codor

是的，我知道tree inorder和preorder遍历和DFS是一样的。我只是困惑，因为实际上在图的实现中，实际上顶点和边都存储在一个数组中，而不像树节点使用指针相互链接。在树中，我们需要遍历字面地访问每个节点。但是，在图中，如果我们需要访问某个节点，似乎循环遍历包含顶点的向量更直接。我想图遍历算法更多地用于检测顶点之间的关系，而不是仅仅访问节点。（？） – Vschon

那么，你也可以在树中做到这一点（你将所有节点的地址存储在一个数组中，然后你可以在任何时间访问它们中的任何一个）。但是，访问一个节点与访问它不是一回事。这更关键的是你如何到达那里。作为程序员，您可以访问所有顶点，但可能发生的情况是您无法“访问”顶点，因为它是孤立的。 – Radu

我尝试了一个玩具程序，使用图遍历算法找到迷宫路径，现在对它的用法有了更好的理解。非常感谢。对，访问与获取物理访问权限是非常不同的。 – Vschon

图遍历算法的用法

回答

相关问题