强连通分量
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
int V; // 顶点个数
list<int> *adj; //邻接表
// 最晚的完成时间的顶点放在栈顶
void fillOrder(int v, bool visited[], stack<int> &Stack);
// DFS打印以v起点的边
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
//打印所有的强连通分量
void printSCCs();
//得到当前图的转置图
Graph getTranspose();
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int> [V];
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
Graph Graph::getTranspose() {
Graph g(V);
for (int v = 0; v < V; v++) {
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i) {
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
void Graph::fillOrder(int v, bool visited[], stack<int> &Stack) {
visited[v] = true;
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
fillOrder(*i, visited, Stack);
//所有从v顶点可达的顶点都已处理完，v顶点访问完成
Stack.push(v);
}
void Graph::printSCCs() {
stack<int> Stack;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// 根据完成时间压入栈中，栈顶是完成时间最晚的顶点
for (int i = 0; i < V; i++)
if (visited[i] == false)
fillOrder(i, visited, Stack);
// 创建转置图
Graph gr = getTranspose();
// 准备第二次DFS
for (int i = 0; i < V; i++)
visited[i] = false;
while (Stack.empty() == false) {
int v = Stack.top();
Stack.pop();
// 打印以v为起点的强连通分量
if (visited[v] == false) {
gr.DFSUtil(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 << "Following are strongly connected components in given graph \n";
g.printSCCs();
return 0;
}
评论