摘要：

1，无向图的连通性介绍

2，并查集判断无向图的连通性

3，Floyd算法判断无向图的连通性

1，无向图的连通性介绍

在无向图中，若任意一对顶点(x,y)，存在从 x 到 y 的路径，则该无向图是连通的，如下图所示，左边的是连通图，右边的不是。

打开网易新闻 查看精彩图片

在有向图中，图的连通性分为强连通图，单向连通图和弱连通图。

1，强连通图：在有向图中，若任意一对顶点(x,y)，都存在从 x 到 y 和 y 到 x 的路径，也就是任意两点相互可达，则该图就是强连通图。

2，单向连通图：在有向图中，若任意一对顶点(x,y)，存在从 x 到 y 或者 y 到 x 的路径，则该图就是单向连通图，要注意这里的任意两个字。

3，弱连通图：如果有向图的底图（不考虑边的方向）是连通的，则该有向图就是若连通图。

打开网易新闻 查看精彩图片

一般情况下讨论图的连通性主要是无向图，而对于有向图我们一般讨论比较多的是强连通分量。计算有向图的强连通分量可以使用kosaraju算法和Tarjan算法，其中Tarjan算法还可以计算图的割点和割边（如果存在割点和割边），这些在后面我们都会介绍。