从给定节点开始有向图的 BFS 遍历
我对图的基本广度优先搜索遍历的理解是：
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 ，我们永远不会打印 a 和 c 。
我在算法中遗漏了什么吗？
我使用了 HashMap
My understanding of basic breadth-first search traversal for a graph is:
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
However, if we have to traverse a directed graph from a given node and not all nodes are accessible from the given node (directly or indirectly), how do we use BFS for traversing the graph of this situation?
Can you please explain in this graph as well:
a=> b => d => e => d
a=> c => d
Here if the starting node is b , we never print a and c.
Am I missing something in the algorithm?
I used HashMap<String, ArrayList> adj = new HashMap(); to create the adjacency list to store graph.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
搜索算法遍历图。如果有无法遍历的边，因此无法到达节点，则搜索将根本找不到它们。
A search algorithm traverses a graph. If you have edges that cannot be traversed and thus nodes that cannot be reached, the search will simply not find them.
您的理解是正确的，除了“从任意节点开始”部分之外——BFS 遍历必须从根节点开始。因此，在您的示例中，您必须从节点 a 开始，否则，正如您所说，您将永远不会访问它。
You are correct in your understanding, except for the "Start from any node" part -- a BFS traversal must begin from the root node. So in your example, you would have to begin with node a, otherwise, as you have said, you will never visit it.