锐客网

  1. 首页 > it技术 > >

Kosaraju算法求有向强连通分量,缩点后是DAG的拓扑序列(从小到大)

强连通分量分解
对于一个有向图顶点的子集S，如果在S内任取两个顶点u和v，都能找到一条从u到v的路径，那么
就称S是强连通的。如果在强连通的顶点集合S中加入其他任意顶点集合后，它都不再是强连通的，
那么就称S是原图的一个强连通分量（SCC:Strongly Connected Component） 。任意有向图都可以
分解成若干不相交的强连通分量，这就是强连通分量分解。把分解后的强连通分量缩成一个顶点，
就得到了一个DAG（有向无环图）。
【Kosaraju算法求有向强连通分量,缩点后是DAG的拓扑序列(从小到大)】Kosaraju算法求有向强连通分量,缩点后是DAG的拓扑序列(从小到大)
文章图片


强连通分量分解可以通过两次简单的DFS实现。第一次DFS时，选取任意顶点作为起点，遍历所
有尚未访问过的顶点，并在回溯前给顶点标号（post order，后序遍历） 。对剩余的未访问过的顶
点，不断重复上述过程。
完成标号后，越接近图的尾部（搜索树的叶子），顶点的标号越小。第二次DFS时，先将所有边
反向，然后以标号最大的顶点为起点进行DFS。这样DFS所遍历的顶点集合就构成了一个强连通
分量。之后，只要还有尚未访问的顶点，就从中选取标号最大的顶点不断重复上述过程。


Kosaraju算法求有向强连通分量,缩点后是DAG的拓扑序列(从小到大)
文章图片


正如前文所述，我们可以将强连通分量缩点并得到DAG。此时可以发现，标号最大的节点就属于
DAG头部（搜索树的根）的强连通分量。因此，将边反向后，就不能沿边访问到这个强连通分量
以外的顶点。而对于强连通分量内的其他顶点，其可达性不受边反向的影响，因此在第二次DFS
时，我们可以遍历一个强连通分量里的所有顶点。
Kosaraju算法求有向强连通分量,缩点后是DAG的拓扑序列(从小到大)
文章图片


该算法只进行了两次DFS，因而总的复杂度是O(|V|+|E|)。

int V; // 顶点数 vector G[MAX_V]; // 图的邻接表表示 vector rG[MAX_V]; // 把边反向后的图 vector vs; // 后序遍历顺序的顶点列表 bool used[MAX_V]; // 访问标记 int cmp[MAX_V]; // 所属强连通分量的拓扑序322 第 4 章 登峰造极——高级篇 void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int v) { used[v] = true; for (int i = 0; i < G[v].size(); i++) { if (!used[G[v][i]]) dfs(G[v][i]); } vs.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (int i = 0; i < rG[v].size(); i++) { if (!used[rG[v][i]]) rdfs(rG[v][i], k); } } int scc() { memset(used, 0, sizeof(used)); vs.clear(); for (int v = 0; v < V; v++) { if (!used[v]) dfs(v); } memset(used, 0, sizeof(used)); int k = 0; for (int i = vs.size() - 1; i >= 0; i--) { if (!used[vs[i]]) rdfs(vs[i], k++); } return k; }




    推荐阅读


    上一篇：马蹄莲

    下一篇：【贪心+堆】锯木