遍历图时节点断开连接

Question

我一直在学习这个链接上的广度优先遍历：
广度优先遍历

如果图的结构变成这样，怎么办：

节点3现在与图断开连接。当使用遍历程序时，它不会显示顶点3。有没有方法可以显示这个顶点？

- Pradeep

---

这个问题在你提供的链接中有直接的解答。请搜索“例子：非连通图”。 - beaker

Answer 1

据我理解，广度优先搜索会在存在未被访问的节点时不断寻找；但如果不这样做，广度优先搜索只会访问初始顶点所在的连通分量中的节点。这似乎更多是定义上的问题而非实际编程问题；只需在存在未被访问的节点时重新启动广度优先搜索实现，如果需要访问所有连通分量。

- Codor

Answer 2

许多BFS/DFS的实现都默认图是连通的。

有没有一种方法可以显示这个顶点？

有的。如果在完成BFS之后仍然有未被访问的顶点，将它们入队。

- Xline

Answer 3

如果您有所有节点的列表，则您选择的图搜索算法（DFS / BFS）将逐个发现连通组件。

您可以按以下方式执行此操作。

例如，考虑您的示例图，其中有4个节点，边缘位于0,2、2,0和1,2之间，而节点3没有传入或传出边缘。

您将拥有节点列表{0，1，2，3}。

为了发现所有连接的组件，您将执行以下操作：

Initialize visited array. Set all nodes to false

for node in list:
    if not visited: dfs(node)

这里的dfs是按照通常的方式实现的。当你在我们的列表{0,1,2,3}上运行代码时，第一个dfs调用将访问节点{0,1,2}，并将标记为已访问的节点为0,1,2。然后当我们遇到3时，由于它没有被访问过，会有另一个dfs调用。

希望你能理解。

- adijo