本文共 3691 字，大约阅读时间需要 12 分钟。
问题描述：
给定一个有向图，设计一个算法，求解并输出该图的各个强连通分量。
❗明确概念❗：
连通性：在无向图中，若从顶点 u 到 v 有路径，则称顶点 u 与 v 是连通的。
强连通图：在有向图中，若对于每一对顶点 u 和 v，都存在一条从 u 到 v 的路径，则称此图是强连通图。
强连通分量 Strongly Connected Component(SCC)：非强连通图的极大强连通子集。
每个有向图关于其强连通部件都是一个有向无环图。?
汇连通分量Sink SCC
源连通分量Source SCC
❗算法描述❗：
1、Testing Strong Connectivity：
Pick any node s.Run BFS from s in G.Run BFS from s in GR(reverse orientation of every edge in G) .Return true if all nodes reached in both BFS executions.Correctness follows immediately from previous lemma.
2、Decomposing a graph into its SCCs：
性质1：如果explore子过程从顶点 u 开始，那么该子过程恰好在从 u 可达的所有顶点都已访问之时终止。
→ if we start in a sink SCC, we will precisely identify that SCC！如果我们从汇强连通分量开始遍历，我们会得到完整的该汇强连通分量中的顶点，不多不少！
→ ❓ 两个问题：
A. How to find a node that is guaranteed to be in a sink SCC ?
B. Once we’ve identified a sink SCC, how do we continue ?
→ ⭐ 解决方法：
Problem (A): we can always find a node that is guaranteed to be in a source SCC!
→ Source SCC in GR = sink SCC in G（很重要的一个技巧）
（? 在判断图是否是强连通图时也用到了反转图的技巧：判断强连通图时，任取有向图G的某结点S，从S开始进行深度优先搜索，若可以遍历G的所有结点，则将G的所有边反向，再次从S开始进行深度优先搜索，如果再次能够遍历G的所有结点，则G是强连通图，两次搜索有一次无法遍历所有结点，则G不是强连通图。）
∴ run DFS on GR and pick node with highest post number; this lies in a sink SCC of G.
Problem (B): Identify sink SCC, delete from graph. Of the remaining nodes, the one with highest post number (in G R ) will be in a sink SCC of whatever is left of G.
/*伪代码*/run DFS on GRfor v in V, in decreasing order of GR-post numbers:if not visited[v]:{ explore(G,v) output nodes seen as a SCC}
? 这个网站的解释很棒 ，网站里的代码也运行成功⭐。全英文注释值得学习！
#include#include #include
using namespace std;class Graph{ int vexnum; // 顶点数量 list *adjlist; // 邻接表 void Poststack(int v, bool visited[], stack &Stack); // 以每个顶点的 post 值的递增顺序将顶点填入栈中 void DFS(int v, bool visited[]); // 从 v 开始，进行 DFSpublic: Graph(int vexnum); // 初始化 void addEdge(int v, int w); // 给图中添加边 void printSCCs(); // 打印强连通分量 Graph getTranspose(); // 得到逆序图};/*初始化*/Graph::Graph(int vexnum){ this->vexnum = vexnum; adjlist = new list [vexnum];}/*给图中添加边*/void Graph::addEdge(int v, int w){ adjlist[v].push_back(w);}/*从 v 开始，进行 DFS*/void Graph::DFS(int v, bool visited[]){ // 改变 v 的状态 visited[v] = true; cout << v << " "; list ::iterator i; for (i = adjlist[v].begin(); i != adjlist[v].end(); ++i) { if (!visited[*i]) { DFS(*i, visited); } }}/*得到逆序图*/Graph Graph::getTranspose(){ Graph g(vexnum); for (int v = 0; v < vexnum; v++) { // 反转所有边 list ::iterator i; for (i = adjlist[v].begin(); i != adjlist[v].end(); ++i) { g.adjlist[*i].push_back(v); } } return g;}/*以每个顶点的 post 值的递增顺序将顶点填入栈中*/void Graph::Poststack(int v, bool visited[], stack &Stack){ visited[v] = true; list ::iterator i; for (i = adjlist[v].begin(); i != adjlist[v].end(); ++i) { if (!visited[*i]) { Poststack(*i, visited, Stack); } } Stack.push(v); return;}/*打印强连通分量*/void Graph::printSCCs(){ stack Stack; bool *visited = new bool[vexnum]; for (int i = 0; i < vexnum; ++i) { visited[i] = false; } // 根据访问结束时间填充栈 - 第一次DFS for (int i = 0; i < vexnum; i++) { if (visited[i] == false) { Poststack(i, visited, Stack); } } // 创建一个逆序图 Graph gr = getTranspose(); // for (int i = 0; i < vexnum; i++) { visited[i] = false; } // 根据栈中的顺序处理所有顶点 while (Stack.empty() == false) { // 弹出post值最大的顶点 int v = Stack.top(); Stack.pop(); // 输出一个强连通分量 if (visited[v] == false) { gr.DFS(v, visited); cout << endl; } }}int main(){ // 建立一个图 Graph g(5); g.addEdge(1, 0); g.addEdge(0, 2); g.addEdge(2, 1); g.addEdge(0, 3); g.addEdge(3, 4); cout << "强连通分量:" << endl; g.printSCCs(); return 0;}
转载地址：http://cxtai.baihongyu.com/