Tarjan算法求解有向图强连通分量

时间复杂度:O(E+V)

如果两个顶点可以相互通达,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

两个重要数组:

dfn: 在DFS中该节点被搜索的次序(时间戳)
low: 为i或i的子树能够追溯到的最早的栈中节点的次序号

当dfn[ i ] == low[ i ]时,为i或i的子树可以构成一个强连通分量。

然后举一个例子来说明一下流程:

《Tarjan算法求解有向图强连通分量》

我们从1号节点来开始dfs的过程,然后逐个走到节点2、3、4,走到4的时候,此时下一个点1,这个点我们已经访问过了(dfn[1] != 0), 并且点1在当前队列里,所以我们用点1的low值即1来更新4的low值,然后回溯到点3,同样用节点4的low值来更新3的low值,同样对2,然后回到1。经过这一波过程后,low[4]=low[3]=low[2]=low[1]=1, 而low[1]==dfn[1]==1,因此我们可以得出1点的子树可以构成一个强连通分量,所以我们只要把当前队列里的点都标记成这个连通分量然后将他们从队列中弹出。

接下来我们就从5号节点来dfs, 下一个节点是6,此时唯一可以继续遍历的节点就是1,而点1之前我们已经处理过了,所以我们就不需要继续处理了,而且由于1点此时已经不在队列里了,所以我们就不需要用1点的low来更新6点了,因此我们可以判断出6点是一个最大联通分量。同理对于节点5.

例题poj2186,题目大意就是给你一堆有向边,例如A->B, B->C, 求有多少个点可以由其它所有点到达。用到一个重要的性质是DAG(有向无环图)只有一个点的出度为0,所以我们只需要把图缩点去环,然后求出这个出度为0对应的那个强连通分量,然后这个强连通分量里的每个点都是满足题意的。

代码:

求解有向图的另一个算法是Kosaju算法,它的思路主要是求两次dfs,第一次是逆图的dfs,第二次是正图的dfs,因为正向能到,反向也能到的才会在同一联通分量里。

另外,tarjan算法可以应用到求无向图的割点和桥中,这篇博客写的不错:https://www.jianshu.com/p/d50ae711f946

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注