有向图的连通性

07 Nov 2022

太少写算法了，基础知识都还给老师了 😅

有向图的连通性有三种：强连通，单向连通，弱连通。

强连通指图中任意两个节点之间都可以相互连通。

单向连通指图中任意两个节点之间存在任意方向的连通，不要求相互连通。

弱连通指如果把有向图的有向边变成无向边后图是连通的，那么就是弱连通。

从上面的关系可以知道，强连通的图一定是单向连通的，单向连通的图一定是弱连通的。

有向图的强连通性判断可以在线性时间内求得：

1. 使用 Tarjan 或 Kosaraju 算法找到所有强连通分量
2. 如果强连通分量数量为 1，则有向图是强连通的

单向连通可以在求得强连通分量后把图变成 DAG，然后判断 DAG 中是否有一个以上的节点的入度为 0。

弱连通性的判断就把所有边都变成无向边然后任选一个节点做深度遍历看能否遍历所有的节点即可。