有向图(6)--计算强连通分量的Kosaraju算法

古城微笑少年丶 2022-08-18 02:42 186阅读 0赞

Kosaraju算法

1.在给定的一幅有向图G中，使用DepthFirstOrder来计算他的反向图R的逆后序排列

2.在G中进行标准的深度优先搜索，但是要按照刚才计算得到的顺序而非标准的顺序来访问所有未被标记的顶点

3.在构造函数中，所有在同一个递归dfs()调用中被访问到的顶点都在同一个**强连通分量**中

#ifndef __KOSARAJU_SCC_H__
    #define __KOSARAJU_SCC_H__
    
    #include "Digraph.h"
    #include "DepthFirstOrder.h"
    
    class KosarajuSCC {
    private:
    	bool* marked;		// 已经访问过的顶点
    	int* id;			// 强连通分量的标识符
    	int count;			// 强连通分量的个数
    
    public:
    	KosarajuSCC(Digraph G);
    	~KosarajuSCC() { delete[] marked; delete[] id; }
    
    	bool stronglyConnected(int v, int w)const { return id[v] == id[w]; }
    	int getId(int v)const { return id[v]; }
    	int getCount()const { return count; }
    
    private:
    	void dfs(Digraph G, int v);
    };
    
    KosarajuSCC::KosarajuSCC(Digraph G) {
    	count = 0;
    	int vNum = G.getV();
    	marked = new bool[vNum];
    	id = new int[vNum];
    	for (int i = 0; i < vNum; ++i) {
    		marked[i] = false;
    		id[i] = i;
    	}
    	// 对反向图进行DFS
    	//DepthFirstOrder order(G.reverse());
    	// 得到逆后序
    	//std::stack<int> stk(order.getReversePost());
    	// 在原图中对逆后序排列进行dfs
    	//while (!stk.empty()) {
    	//	if (!marked[stk.top()]) {
    	//		dfs(G, stk.top());
    	//		++count;
    	//	}
    	//	stk.pop();
    	//}
    
    	// 第二种做法
    	// 对原图进行DFS
    	DepthFirstOrder order(G);
    	// 得到逆后序
    	std::stack<int> stk(order.getReversePost());
    	// 获得反向图
    	Digraph R = G.reverse();
    	// 在反向图中对逆后序排列进行dfs
    	while (!stk.empty()) {
    		if (!marked[stk.top()]) {
    			dfs(R, stk.top());
    			++count;
    		}
    		stk.pop();
    	}
    }
    
    void KosarajuSCC::dfs(Digraph G, int v) {
    	marked[v] = true;
    	id[v] = count;
    	for (int w : G.getAdj(v)) {
    		if (!marked[w])
    			dfs(G, w);
    	}
    }
    
    
    #endif

\-main.cpp 测试用例

#include "KosarajuSCC.h"
    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int vNum, eNum;
    	cin >> vNum >> eNum;
    
    	Digraph G(vNum);
    	int v, w;
    	for (int i = 0; i < eNum; ++i){
    		cin >> v >> w;
    		G.addEdge(v, w);
    	}
    	
    	KosarajuSCC k(G);
    	cout << k.getCount() << " copmonents" << endl;	// 强连通分量个数
    	
    	vector<list<int> > vlst(k.getCount());
    	for (int i = 0; i < vNum; ++i) {
    		vlst[k.getId(i)].push_back(i);
    	}
    	for (list<int> lst : vlst) {
    		for (int v : lst) {
    			cout << v << " ";
    		}
    		cout << endl;
    	}
    	
    	return 0;
    }

![SouthEast][]

[SouthEast]: /images/20220731/b4cea311b3594da0ab560c46d5d3b8eb.png