图的连通性

无向图的深度优先搜索

深度优先搜索的算法过程

在图上做DFS时，我们从某个点出发，递归地访问所有与该节点有边相连的节点。在这个过程中，我们用数组vis记录下每个点是否被访问过，在每次访问相邻节点的时候只访问那些没有被访问过的，由此来保证每个节点只被访问一次。如果我们不停找没有被访问过的节点进行DFS，直到所有节点都被访问，我们发现这个过程中每个点恰好被访问一次，而每条边恰好被访问两次（分别被边所连接的节点访问一次），因此进行一次完整的DFS的复杂度是\(O(|V|+|E|)\)。

直觉就可以发现，对某个点出发DFS之后被访问到的节点恰好就是与这个点相连通的所有点。我们可以通过归纳法证明每个与该点连通的点都会被访问，以及每个被访问的点都与该点连通，来严格地说明这一点。如果该点被访问，那么“恢复出递归的过程”就可以找到这样一条路径；如果该点有路径却没有被访问，那么所有指向终点的点也都没被访问，所有指向指向终点的点的点也没被访问，最后发现起点也没被访问，矛盾。

DFS树

任何一个递归的过程都可以找到一个“树”来与它同构地对应。在无向图的DFS中，对应的就是“DFS树”。在DFS树上，节点就是图的节点，而树边恰好是那些“被我们用来到达这些节点”的边。所以DFS树是原图的一颗生成树，而那些“非树边”横跨在树上的节点之间，它们之所以没能成为树边是因为它们指向的节点在DFS的过程中已经被“事先访问过”了。

更深入的研究DFS树会给我们带来很多的发现。为了更好的看清DFS树的结构，我们在算法的过程中用一个变量\(t\)来“计时”。当我们第一次到达某个节点\(i\)的时候，我们取出\(t\)的值记为\(pre[i]\)，并让\(t++\)。而当\(i\)的所有递归都完成时，我们再次取出\(t\)的值，记为\(post[i]\)，并也让\(t++\)。这样，每个点的\([pre[i],post[i]]\)就形成了时间上的一段区间，DFS树上的每个节点的区间都恰好包含住了它的各个儿子节点的区间（这让我联想到线段树，但是是多叉的线段树；也让我想到偏序集）。

有向图的深度优先搜索

边的分类

相对于无向图来说，从有向图上某点出发DFS所能到达的节点是哪些，是不太直观的。尽管如此，“所有被访问的节点恰好是所有从该点出发有路径能到达的节点”这个结论依然是成立的（证明和无向图中相同，事实上那个证明在有向图中更有意义），并且我们依然在这些节点上画出DFS树。此时，我们有必要对非树边进行更精细的分类：有一类边从一个节点向下指向它的某个后代节点，称为forward edge；另一类边从某个几点指向它的某个祖先节点，称为把back edge；还有一类边横跨两棵子树，即连接着两个自身不作为LCA的节点，称为cross edge。如果在DFS的过程中计时，时间区间依然满足无向图中的那种包含的性质。

有向图有环当且仅当DFS树上存在back edge。因为“环”要求环上的点两两可达，如果我们去掉其中一条边，那么我们会形成一条链，链的一段一定能通到另一端。因此，这条链在DFS树上一定是从某个节点延伸到某个后代节点的一条链。因此我们刚才去掉的那条边必定是一条back edge。也就是说任意一个环都包含着一条back edge。所以如果没有back edge，图上一定就没有环。而如果图上存在一条back edge，那么链加上这条back edge就已经形成了一个环。

DAG，拓扑排序

如果有向图上没有环，即如果不存在任何back edge，那么这张图就被称为有向无环图（DAG）。DAG很像被“压缩起来的树”，因为它看上去反映了节点之间的某种顺序结构（再一次，我联想到偏序集）。为此，我们想给所有点排序，形成排列\(\sigma\)，要求任意\(i<j\)，如果\(\sigma_i,\sigma_j\)间有路径可达，就必须是\(\sigma_i\)出发到达\(\sigma_j\)（由于没有环，这就意味着\(\sigma_j\)出发一定无法到达\(\sigma_i\)）。从偏序集的角度来看，要求任何两个可比较偏序关系的节点，小的一定要出现在大的前面。DAG节点的这种顺序称为“拓扑序”，这个过程也称为图的“线性化”。

我们已经研究清楚了树边上\(pre,post\)的关系，这个关系可以表达为对于任何树边\(u \to v\)，一定有\(pre[u]<pre[v]<post[v]<post[u]\)。而对于非树边，\(u,v\)之间没有包含关系了。联想线段树的结构，我们两个时间区间不是包含就是无交，不可能有交集。而非树边中必然有\(v\)比\(u\)先访问，因此得出关系\(pre[v]<post[v]<pre[u]<post[u]\)。

于是我们观察到，无论是何种边，DAG中任意一条边始终有\(post[v] <post[u]\)成立。因此\(post\)实际上就是我们所要的拓扑序！只不过在拓扑序中，我们宁愿让\(v\)的排名靠后，所以我们把\(post\)倒过来，得到结论：DAG的拓扑序是\(post\)序的倒序。

以上关系（边的\(post\)关系）不仅对于一次DFS所能到达的节点成立，如果我们不断找到一个没访问过的节点出发做DFS，上述关系始终成立。因为任何时候，只要两个时间区间没有交叉，拓扑序就是\(post\)序的关系就成立。而我们已经有充分的理由说明时间区间是不可能交叉的了。

根据这个结论也可以用另一种不基于DFS的算法来做拓扑排序：如果我们有一种快速的做法找到一个图中\(post\)最大的点，然后把它连通与它相连的边从图中删去，递归地求解余下的图的拓扑序，我们也能求出整张图的拓扑序。这里要注意，不同的DFS方式（例如在选择一个点的相邻边的时候的顺序）会产生不同的DFS树，因此也就会产生不同的\(post\)序。DFS树从来都不是唯一的，从而拓扑序也不是唯一的。当我们不想做DFS时，我们说的最大的\(post\)就是指，不存在任何一个节点\(post\)比它大，只要满足这个条件的节点一定可以作为“某个”DFS树上\(post\)最大的节点（这只是猜测）。我们断言，当一个点的入度为0就一定可以作为\(post\)最大的节点。设这个点为\(u\)，我们可以通过上帝视角先从\(u\)出发DFS，能访问到的点集记为\(S\)。当我们真正开始DFS的时候，我们先从所有\(S\)以外的点出发。我们能保证这个过程中我们永远不能到达\(u\)，因为根本没有边会是指向\(u\)的。因此到最后，我们就从\(u\)出发DFS，这样就能保证\(u\)一定是\(post\)最大的节点。这样我们就证明了，任何一个入度为0的点都可以作为某个拓扑序中排名第一的节点。

还要补充说明一点，任何一张DAG上一定存在入度为0的点。我们可以这样想象：从某个点出发，如果它入度不为0，就沿着这条入边到达那个节点。不断重复这个过程，要求不能访问重复的点。如果某一时刻入度为0了，那么就结束；如果某一时刻入度不为0但所有想去的节点都已经被访问过了，这说明一定出现了环，矛盾；如果永远没有碰到以上两种情况，我们就会访问无穷个节点，这与点的个数有限矛盾了。同样的也可以证明，任何一张DAG上也一定存在出度为0的点。

强连通分量

为了更好地看清有向图中的连通性关系，我们在有向图中寻找像无向图的连通块那样的“两两可达的”点的集合。如果有向图中某个这样的点的集合达到了极大，即再往里面加任何一个点都将破坏这种“两两可达”性，就称这个点集为一个“强连通分量”。每个点都归属于某个强连通分量，如果非常不幸，这个点可能仅由它自己就构成了一个强连通分量。由此，我们来试图改造有向图的相貌。如果我们把每个强连通分量中的点缩成一个点，这样强连通分量内部的边就消失了，余下的边让他们对应地连接相应的强连通分量，那么我们就得到了一张新的图。一个非常重要的事实是，这张图里一定没有环了！如果有，那么这个环上的任意两个“点”之间两两可达，而“点”作为原图中的强连通分量内部一定两两可达，这就意味着所有这些点的集合在原图中两两可达了，这就和强连通分量的“极大”，矛盾了。因此，我们得到的这张新图是一张DAG！至此，有向图的连通性已经被表现得非常清晰了。

下面的问题的是，如何来找出所有的强连通分量。假设我们有上帝视角，已经把这张缩点后的DAG画出来了。这张DAG上有一些出度为0的点。从这个点内部的某个原图中的点出发DFS，由于有向图“DFS访问到的节点恰好是所有有路径可达的点”这一性质，我们访问到的节点恰好就是这整个强连通分量。那么不断地删去DAG上出度为0的强连通分量，我们就能找出所有强连通分量。那么唯一的问题是，如何在原图上找到这个“出度为0的强连通分量”。

一种算法是把所有边反向，构成反图\(G^R\)。边的反向并不会改变强连通分量，因此只需把缩点后的DAG的所有边也反向就会得到这个反图的DAG。如果一个点在原图中是入度为0的，那么在DAG中势必也是入度为0的（否则在原图中就不可能入度为0）。而在原图中，这个点就位于出度为0的强连通分量中。因此我们在原图\(G\)中从这个点出发DFS，所得到的点集恰好就是我们要找的连通分量了。

另一个算法是Tarjan算法。由于有向图DFS树中back edge和cross edge的存在，某个点出发能够走到\(pre\)值比它小的点。我们记录下每个点所能到达的\(pre\)最小的节点。我们在DFS过程中让每个已经完成递归的节点入栈。我们在缩点后的DAG上想一想，当我们第一次DFS过程中如果某节点在递归完毕（特别注意是完毕，所以我们思考的顺序是从叶子到根）后发现它所能到达的\(pre\)最小的节点就是它自己，那么当前栈内的节点就恰好是一个完整的出度为0的强连通分量！我们让这些节点出栈，并且由于我们不会再访问这些节点，这一部分就好像从原图中消失了一样。所以我们继续上述过程，每一次都好像是在一张新图中“第一次”发现了出度为0的强连通分量一样。我们通过递归“模拟出了把已经找到的出度为0的连通分量从原图中删掉”的效果，由此一步一步找出了所有的强连通分量。