无向连通图

Question

我很困惑无向图是否可以被认为是连通的？

例如：

A---B---C

假设我们有三个顶点A、B、C。如果这个图像上图一样是无向的，它是连通的吗？ A到达B，但到达C了吗？

另一个例子：

A--->B<---C

我说这个有向图不连通是因为 A 无法到达 C 对吗？因为在我看来这张图不是多向的。

另一个例子：

A---B C---B

这个无向图会连通吗？

哪位大侠能详细解释一下，万分感谢

Answer 1

连通图意味着我们可以通过一些路径到达图中的每个节点。以下面的图为例，它是连通的，因为我们可以到达图中的每个节点

    0 --- 1-------5----6--8
    | \    \      |   /  /
    |  \    \     |  /  /
    |   \    \    | /  /
    2    3----4---7---9

然而像这样的图表

    0 --- 1-------5----6  8
    | \    \      |   /  /
    |  \    \     |  /  /
    |   \    \    | /  /
    2    3----4---7   9

已断开连接，因为无法到达 8 和 9。检查图是否已连接的一种简单方法是使用已访问节点的布尔值。 运行 bfs 或 dfs，只要你在一个节点上，就把它标记为已访问。当您的算法完成后 运行，如果所有顶点都未被访问，那么您的图将断开连接。

从你的例子来看，第一张图A---B---C是连通的
第二张图 A--->B<---C 是断开的，因为没有从 A 到 C 的路径。如果我们 运行 bfs/dfs 在这上面我们不能访问所有的顶点
第三个图 A---B C---B 也是断开的，因为它们是两个单独的图。