2

我对图的基本广度优先搜索遍历的理解是：

BFS        
    Start from any node. 
    Add it to queue. 
    Add it to visited array.

    While queue is not empty:
        Remove head from queue; 
        Print node.

        add all unvisited direct subchilds to que; 
        mark them as visited

但是，如果我们必须从给定节点遍历有向图，并且并非所有节点都可以从给定节点访问（直接或间接），那么我们如何使用 BFS 来遍历这种情况的图呢？

您能否在此图中也解释一下： 

a=> b => d => e => d  
a=> c => d

在这里，如果起始节点是b，我们从不打印aand c。

我在算法中遗漏了什么吗？

我曾经 HashMap<String, ArrayList> adj = new HashMap();创建邻接列表来存储图形。

4

2 回答 2

1

但是，如果我们必须从给定节点遍历 DIRECTED 图，并且并非所有节点都可以从给定节点 [直接或间接] 访问，那么我们如何使用 BFS 来实现。

搜索算法遍历图。如果您有无法遍历的边并因此无法到达节点，则搜索将根本找不到它们。

于 2010-04-06T04:07:25.900 回答
0

您的理解是正确的，除了“从任何节点开始”部分 - BFS 遍历必须从根节点开始。因此，在您的示例中，您必须从节点 a 开始，否则，正如您所说，您将永远不会访问它。

于 2010-04-06T04:06:43.420 回答