【图论2-4】连通性问题

对应进阶篇第 12 章。 在之前的章节中已经讨论过最短路问题和生成树问题了。在无向图中，连通性问题可以使用 并查集解决。但是当删去某个点或某条边时，如何判断图是否连通？对于无向图来说，有一些点 或者是边是“关键”的，没有这些点或者边，这个图就会分裂成各个部分。 无向图中连通的点可以相互到达，那么有向图上可以相互到达的点对有什么性质呢？有序性 是一个很好的性质，但对于多数错综复杂的有向图来说并不能直接进行拓扑排序。可以将一些可 以互相到达的点合并成一个点，使这个有向图变为有向无环图，即可进行拓扑排序。 本章会分别介绍无向图的双连通性和有向图的强连通性。