Tarjan算法用于有向图,用于找强连通区域,割边等,属于图论内容。
它的思路类似于DFS + Union Find, 下面来详细介绍:
图和详细视频参考链接
首先任意选一点作为起点做DFS,DFS的过程中要给各node标上id 然后每个node有一个low link value, 简单解释这是表示当前node能到达的node中最小的id(包括它自己的id) 比如node1,它能到达的node中最小id是0 node2 和 3能到达的最小id是2,同理4,5 好了,现在概念清楚了, 我们可以看到有相同low link value的node在一个强连通区域。
下面要解决的问题是怎么样在DFS的过程中更新low link value。
首先我们认识到当node的id和它的low link value相同时,说明又回到了起点,进入了SCC(强连通区域), 比如node 0, 2, 4
DFS需要一个stack装入现在正在访问的node, 还要一个visited数组记录node是否已经被访问过,防止重复遍历。
从任意的0点出发,DFS 像下图这样,正在访问的0,1,2压入stack, 然后出现了在0处,它的id和low link value相同,说明进入了SCC,开始回溯, 回溯的时候更新stack.top点的low link value, 就是node 2, 2和0是相通的,都在stack里,所以2的low link value和 node 0 应该相同,更新lowlink[2], 把当前SCC的node全部从stack中取出,更新low link value 然后任选另一起点继续上面的过程, 然后到node 5的时候,又到了0,但是现在0不在stack里面,所以不更新low link value。 同理经过node 6到了node 2, node 2不在stack里面,所以也不更新low link value 然后到node 4, node 4的id和low link value相等,所以开始回溯。 得到第2个SCC 虽然node 3的id和low link value相同,但是还不能判断SCC,因为node还没访问完呢,
最后找到了所有的SCC
|