我对图的基本广度优先搜索遍历的理解是:
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<String, ArrayList> adj = new HashMap();
创建邻接列表来存储图形。 最佳答案
然而,如果我们必须从一个给定的节点遍历一个有向图,而不是所有的节点都可以从给定的节点[直接或间接]访问,我们如何使用bfs来实现相同的功能。
搜索算法遍历图形如果有无法遍历的边,因此无法访问节点,则搜索将无法找到它们。