建议先关注、点赞、收藏后再阅读。
判断无向图的连通性可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来实现。
深度优先搜索（DFS）：
算法步骤：
- 选择一个顶点作为起始顶点，标记为已访问。
- 对于起始顶点的每个相邻顶点，如果该相邻顶点未被访问，则继续递归调用DFS进行访问。
- 重复上述步骤，直到所有顶点都被访问过。
- 判断是否有未被访问过的顶点，若有则表示图不是连通的，否则表示图是连通的。
示例：
假设有以下无向图：
代码语言：txt复制 1------2------7
| | /
| | /
5------3---6
|
|
4选择顶点1作为起始顶点，进行DFS。
结果：
代码语言：txt复制 1------2------7
| | /
| | /
5------3---6
|
|
4所有顶点都被访问过，因此该无向图是连通的。
在有向图中找到所有的强连通分量：
强连通分量（Strongly Connected Component，SCC）指的是有向图中的一个最大子图，该子图内的任意两个顶点均可达。要找到所有的强连通分量，可以使用Tarjan算法。
Tarjan算法步骤：
- 对有向图进行深度优先搜索（DFS）。
- 在搜索的过程中，记录每个顶点的访问次序（dfs序）和能够到达的最小次序（low值）。
- 建立一个栈，用来保留搜索过程中访问的顶点。
- 在每个顶点访问结束时，判断该顶点的low值是否等于其dfs序，若相等，则将该顶点及其之前的顶点全部出栈，组成一个强连通分量。
- 重复上述步骤，直到所有顶点都被访问过。
示例：
假设有以下有向图：
代码语言：txt复制 1---->2<----7
| /| ^
| / v |
5-->3 6--->4使用Tarjan算法找到所有的强连通分量。
结果：
代码语言：txt复制 1 7
| /
| /
2<---3--->6
|
v v
5------->4有向图的强连通分量为：{1,2,3,5}，{6}，{4}，{7}。
