利用Tarjan算法求有向图的强连通分量


论文写作或者计算需要帮助可发邮件到 hwstu # sohu.com 把 #替换成@,请说清来意,不必拐弯抹角,浪费相互之间的时间。

返回首页


此处输入要素的个数:


Tarjan算法是用于求有向图的强连通分量

Tarjan算法的用途之一是,求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大强连通分量。

时间复杂度:O(M+N) 注:M代表边数,N代表顶点数。

步骤概要:

步骤1: 找一个没有被遍历过的顶点v,进行步骤2(v)(遍历时间由1开始累加,若是非连通图,则须重复进行步骤1)。否则,算法结束。

步骤2(v): 初始化dfn[v]和low[v]的值为当前的遍历时间,并且v进栈;

对于v所有的邻接顶点u:
(1) 如果u没有被遍历过,则进行步骤2(u),同时维护low[v]。
(2) 如果u已经被遍历过,但还在栈中(即还不属于任一强连通分量),则维护low[v],否则不做任何操作。
   如果有dfn[v]==low[v],则把栈中的顶点弹出(直到把v都弹出为止),这些顶点组成一个强连通分量。

简要证明:

1. 在栈里,当dfs遍历到v,而且已经遍历完v所能直接到达的顶点时,low[v]=dfn[v]时,v一定能到达栈里v上面的顶点:
因为当dfs遍历到v,而且已经dfs递归调用完v所能直接到达的顶点时(假设上面没有low=dfn),这时如果发现low[v]=dfn[v],栈上面的顶点一定是刚才从顶点v递归调用时进栈的,所以v一定能够到达那些顶点。

2 .dfs遍历时,如果已经遍历完v所能直接到达的顶点而low[v]=dfn[v],我们知道v一定能到达栈里v上面的顶点,这些顶点的low一定小于 自己的dfn,不然就会出栈了,也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量,如果它不是极大强连通分量的话low[v]也一定小于dfn[v](这里不再详细说),所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。
强烈推荐详细的解释与说明


显示的是一个随机 12 * 12 的方阵



   老鼠金牛白虎狡兔青龙毒蛇骏马小羊猕猴山鸡狗仔笨猪
老鼠          1    1             1   
金牛                                    
白虎                1 1               
狡兔    1                1            
青龙       1                           
毒蛇                                    
骏马       1    1             1      
小羊          1                        
猕猴    1                         1   
山鸡          1                        
狗仔          1 1             1      
笨猪                         1         
  开始用深度搜索,从第一个节点开始!
      访问的元素是:老鼠
      堆栈里的元素有:老鼠
      数组dfn中各个要素的值:老鼠=1
      数组dfn中各个要素的值:老鼠=1
      访问的元素是:狡兔
      堆栈里的元素有:老鼠、狡兔
      数组dfn中各个要素的值:老鼠=1、狡兔=2
      数组dfn中各个要素的值:老鼠=1、狡兔=2
      访问的元素是:金牛
      堆栈里的元素有:老鼠、狡兔、金牛
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3
          此时金牛在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、狡兔、金牛
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3
          弹出要素金牛 如果不等于金牛继续弹出
         堆栈里的元素有:老鼠、狡兔
          停止弹出!
      访问的元素是:小羊
      堆栈里的元素有:老鼠、狡兔、小羊
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4
          要素狡兔在dfn数组中的值,小于小羊在low数组中的值,现在进行赋值 low小羊=dfn狡兔;
          此时狡兔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、狡兔、小羊
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2
          弹出要素小羊 如果不等于狡兔继续弹出
         堆栈里的元素有:老鼠、狡兔
          弹出要素狡兔 如果不等于狡兔继续弹出
         堆栈里的元素有:老鼠
          停止弹出!
      访问的元素是:毒蛇
      堆栈里的元素有:老鼠、毒蛇
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5
          此时毒蛇在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、毒蛇
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5
          弹出要素毒蛇 如果不等于毒蛇继续弹出
         堆栈里的元素有:老鼠
          停止弹出!
      访问的元素是:狗仔
      堆栈里的元素有:老鼠、狗仔
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6
      访问的元素是:青龙
      堆栈里的元素有:老鼠、狗仔、青龙
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7
      访问的元素是:白虎
      堆栈里的元素有:老鼠、狗仔、青龙、白虎
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=8
      访问的元素是:骏马
      堆栈里的元素有:老鼠、狗仔、青龙、白虎、骏马
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9
          要素白虎在dfn数组中的值,小于骏马在low数组中的值,现在进行赋值 low骏马=dfn白虎;
          要素青龙在dfn数组中的值,小于骏马在low数组中的值,现在进行赋值 low骏马=dfn青龙;
      访问的元素是:山鸡
      堆栈里的元素有:老鼠、狗仔、青龙、白虎、骏马、山鸡
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=7、山鸡=10
          此时山鸡在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、狗仔、青龙、白虎、骏马、山鸡
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=7、山鸡=10
          弹出要素山鸡 如果不等于山鸡继续弹出
         堆栈里的元素有:老鼠、狗仔、青龙、白虎、骏马
          停止弹出!
          要素骏马在low数组中的值,小于白虎在low数组中的值,现在进行赋值让两个相等
          此时青龙在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、狗仔、青龙、白虎、骏马
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10
          弹出要素骏马 如果不等于青龙继续弹出
         堆栈里的元素有:老鼠、狗仔、青龙、白虎
          弹出要素白虎 如果不等于青龙继续弹出
         堆栈里的元素有:老鼠、狗仔、青龙
          弹出要素青龙 如果不等于青龙继续弹出
         堆栈里的元素有:老鼠、狗仔
          停止弹出!
          此时狗仔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠、狗仔
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10
          弹出要素狗仔 如果不等于狗仔继续弹出
         堆栈里的元素有:老鼠
          停止弹出!
          此时老鼠在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10
          弹出要素老鼠 如果不等于老鼠继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:猕猴
      堆栈里的元素有:猕猴
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10、猕猴=11
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10、猕猴=11
          此时猕猴在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:猕猴
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10、猕猴=11
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10、猕猴=11
          弹出要素猕猴 如果不等于猕猴继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:笨猪
      堆栈里的元素有:笨猪
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10、猕猴=11、笨猪=12
      数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10、猕猴=11、笨猪=12
          此时笨猪在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:笨猪
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=4、毒蛇=5、狗仔=6、青龙=7、白虎=8、骏马=9、山鸡=10、猕猴=11、笨猪=12
        数组dfn中各个要素的值:老鼠=1、狡兔=2、金牛=3、小羊=2、毒蛇=5、狗仔=6、青龙=7、白虎=7、骏马=7、山鸡=10、猕猴=11、笨猪=12
          弹出要素笨猪 如果不等于笨猪继续弹出
         堆栈里的元素有:
          停止弹出!
   金牛 小羊 狡兔 毒蛇 山鸡 骏马 白虎 青龙 狗仔 老鼠 猕猴 笨猪
金牛                                   
小羊      1                           
狡兔1 1                              
毒蛇                                   
山鸡      1                           
骏马            1    1 1            
白虎         1    1                  
青龙                  1               
狗仔      1    1       1            
老鼠      1 1             1         
猕猴1                      1         
笨猪                              1   

计算出来后的


老鼠要素
金牛要素
白虎要素
狡兔要素
青龙要素
毒蛇要素
骏马要素
小羊要素
猕猴要素
山鸡要素
狗仔要素
笨猪要素
第0层
第1层
第2层
第3层
第4层
第5层
第6层
第7层
第8层

化学加平台
解释结构模型
感谢化学加提供单独服务器服务器!请大家多支持化学加平台,可以多介绍人关注化学加!
对解释结构模型在线计算有什么意见与建议请发电子邮件到, hwstu #sohu.com 把#替换成 @