首页 > 图论 > 连通性问题 > 求强连通分量(1)-Kosaraju算法
2014
08-25

求强连通分量(1)-Kosaraju算法

强连通分量

有向图强连通分量在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

如下面的图,虽然不是强连通图,但是有3个强连通分量,都用红色框标注。

SCC

Kosaraju算法Tarjan算法Gabow算法皆为寻找有向图强连通分量的有效算法。但是在Tarjan 算法和 Gabow 算法的过程中,只需要进行一次的深度优先搜索,而Kosaraju算法需要两次DFS,因而相对 Kosaraju 算法较有效率。这些算法可简称为SSC(strongly connected components)算法;

Kosaraju 算法即为算法导论一书给出的算法,比较直观和易懂。这个算法可以说是最容易理解,最通用的算法,其比较关键的部分是同时应用了原图G和反图GT。 它利用了有向图的这样一个性质,一个图和他的transpose graph(边全部反向)具有相同的强连通分量!

SCCGraph2

算法思路:

1, DFS遍历原图,对每个访问到的节点标记时间戳(访问完成时间)。

2, 按照时间戳的降序DFS遍历反向图,得到的每个连通块就是一个强连通分量。

算法步骤如下:

1) 创建一个空的栈 ‘S’ ,然后对图做DFS遍历. 在顶点访问完成后加入栈中。访问完成是说回溯返回时,而不是第一次发现该节点时。fillOrder()函数
2) 得到图转置,即将所有边反向。
3) 从S中依次弹出每个顶点,设为 ‘v’. 将v看做遍历的源点 (调用 DFSUtil(v)). 做第二次DFS遍历,可以找到以v为起点的强连通分量,打印出即可。

代码实现如下:

#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;
}

 时间复杂度

DFS遍历的时间复杂度为O(V+E) ,图的转置也为O(V+E) 。因此总的时间复杂度为O(V+E)。

从渐进分析来说,这个复杂度是最好的,但是用到了两次DFS遍历,还有一个常见的更高效的算法 Tarjan’s algorithm ,后面再做讨论。

应用

在社交网络上,有些群体可能是强连通的(例如一个班级的学生),这些群体中的人一般会有一些共同感兴趣的页面或游戏,可以使用SSC算法来找到这样的群体,然后推荐相关的页面或游戏。

参考:http://www.geeksforgeeks.org/strongly-connected-components/


  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。