三种方法求强连通分量的比较


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

返回首页


此处输入要素的个数:


三种方法求强连通分量的比较


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



   老鼠金牛白虎狡兔青龙毒蛇骏马小羊猕猴山鸡狗仔笨猪
老鼠                                    
金牛 1    1 1                1      
白虎                1 1               
狡兔                                    
青龙          1                      1
毒蛇          1                      1
骏马    1       1                     
小羊       1                1         
猕猴                                    
山鸡    1                              
狗仔                                    
笨猪                   1          1   
  访问的元素是:老鼠->
     ; 正在搜索,堆栈里的元素有:老鼠
当前深度搜索堆栈里面的节点是老鼠
  访问的元素是:金牛->
  访问的元素是:白虎->
  访问的元素是:毒蛇->
  访问的元素是:狡兔->
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔
  访问的元素是:笨猪->
  访问的元素是:骏马->
  访问的元素是:青龙->
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马
  访问的元素是:狗仔->
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎
  访问的元素是:山鸡->
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛
当前深度搜索堆栈里面的节点是老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛
  访问的元素是:小羊->
  访问的元素是:猕猴->
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛、猕猴
     ; 正在搜索,堆栈里的元素有:老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛、猕猴、小羊
当前深度搜索堆栈里面的节点是老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛、猕猴、小羊
堆栈里面的节点是老鼠、狡兔、青龙、骏马、狗仔、笨猪、毒蛇、白虎、山鸡、金牛、猕猴、小羊
逆图也就是转置矩阵如下:
   老鼠金牛白虎狡兔青龙毒蛇骏马小羊猕猴山鸡狗仔笨猪
老鼠    1                              
金牛                   1       1      
白虎    1                1            
狡兔    1       1 1                  
青龙                   1               
毒蛇       1                           
骏马       1                         1
小羊                                    
猕猴                      1            
山鸡    1                              
狗仔                                  1
笨猪             1 1                  
  把元素:小羊弹出->
     ; 回路0里的元素有:小羊
  回路序号1加一
  把元素:猕猴弹出->
     ; 回路1里的元素有:猕猴
  回路序号2加一
  把元素:金牛弹出->
     ; 回路2里的元素有:金牛
     ; 回路2里的元素有:金牛、骏马
     ; 回路2里的元素有:金牛、骏马、白虎
     ; 回路2里的元素有:金牛、骏马、白虎、笨猪
     ; 回路2里的元素有:金牛、骏马、白虎、笨猪、青龙
     ; 回路2里的元素有:金牛、骏马、白虎、笨猪、青龙、毒蛇
     ; 回路2里的元素有:金牛、骏马、白虎、笨猪、青龙、毒蛇、山鸡
  回路序号3加一
  把元素:山鸡弹出->
  把元素:白虎弹出->
  把元素:毒蛇弹出->
  把元素:笨猪弹出->
  把元素:狗仔弹出->
     ; 回路3里的元素有:狗仔
  回路序号4加一
  把元素:骏马弹出->
  把元素:青龙弹出->
  把元素:狡兔弹出->
     ; 回路4里的元素有:狡兔
  回路序号5加一
  把元素:老鼠弹出->
     ; 回路5里的元素有:老鼠
  回路序号6加一
  开始用深度搜索,从第一个节点开始!
      访问的元素是:老鼠
      堆栈里的元素有:老鼠
      数组dfn中各个要素的值:老鼠=1
      数组dfn中各个要素的值:老鼠=1
          此时老鼠在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠
        数组dfn中各个要素的值:老鼠=1
        数组dfn中各个要素的值:老鼠=1
          弹出要素老鼠 如果不等于老鼠继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:金牛
      堆栈里的元素有:金牛
      数组dfn中各个要素的值:老鼠=1、金牛=2
      数组dfn中各个要素的值:老鼠=1、金牛=2
      访问的元素是:白虎
      堆栈里的元素有:金牛、白虎
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3
      访问的元素是:毒蛇
      堆栈里的元素有:金牛、白虎、毒蛇
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4
      访问的元素是:狡兔
      堆栈里的元素有:金牛、白虎、毒蛇、狡兔
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5
          此时狡兔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:金牛、白虎、毒蛇、狡兔
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5
          弹出要素狡兔 如果不等于狡兔继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇
          停止弹出!
      访问的元素是:笨猪
      堆栈里的元素有:金牛、白虎、毒蛇、笨猪
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6
      访问的元素是:骏马
      堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7
          要素金牛在dfn数组中的值,小于骏马在low数组中的值,现在进行赋值 low骏马=dfn金牛;
      访问的元素是:青龙
      堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=2、青龙=8
          要素笨猪在dfn数组中的值,小于青龙在low数组中的值,现在进行赋值 low青龙=dfn笨猪;
          要素骏马在low数组中的值,小于笨猪在low数组中的值,现在进行赋值让两个相等
      访问的元素是:狗仔
      堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、狗仔
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9
          此时狗仔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、狗仔
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9
          弹出要素狗仔 如果不等于狗仔继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙
          停止弹出!
          要素笨猪在low数组中的值,小于毒蛇在low数组中的值,现在进行赋值让两个相等
          要素毒蛇在low数组中的值,小于白虎在low数组中的值,现在进行赋值让两个相等
      访问的元素是:山鸡
      堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、山鸡
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=10
          要素金牛在dfn数组中的值,小于山鸡在low数组中的值,现在进行赋值 low山鸡=dfn金牛;
          此时金牛在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、山鸡
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=2
          弹出要素山鸡 如果不等于金牛继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙
          弹出要素青龙 如果不等于金牛继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪、骏马
          弹出要素骏马 如果不等于金牛继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇、笨猪
          弹出要素笨猪 如果不等于金牛继续弹出
         堆栈里的元素有:金牛、白虎、毒蛇
          弹出要素毒蛇 如果不等于金牛继续弹出
         堆栈里的元素有:金牛、白虎
          弹出要素白虎 如果不等于金牛继续弹出
         堆栈里的元素有:金牛
          弹出要素金牛 如果不等于金牛继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:小羊
      堆栈里的元素有:小羊
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10、小羊=11
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=2、小羊=11
      访问的元素是:猕猴
      堆栈里的元素有:小羊、猕猴
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10、小羊=11、猕猴=12
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=2、小羊=11、猕猴=12
          此时猕猴在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:小羊、猕猴
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10、小羊=11、猕猴=12
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=2、小羊=11、猕猴=12
          弹出要素猕猴 如果不等于猕猴继续弹出
         堆栈里的元素有:小羊
          停止弹出!
          此时小羊在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:小羊
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、毒蛇=4、狡兔=5、笨猪=6、骏马=7、青龙=8、狗仔=9、山鸡=10、小羊=11、猕猴=12
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=2、毒蛇=2、狡兔=5、笨猪=2、骏马=2、青龙=6、狗仔=9、山鸡=2、小羊=11、猕猴=12
          弹出要素小羊 如果不等于小羊继续弹出
         堆栈里的元素有:
          停止弹出!
  开始用深度搜索,从第一个节点开始!
      访问的元素是:老鼠
      搜索树里的元素的顺序是:老鼠=>1
      堆栈stack_1里的元素有:老鼠
      堆栈stack_path要素有:老鼠
      弹出堆栈stack_path要素:老鼠
      弹出堆栈stack_1要素:老鼠
      访问的元素是:金牛
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2
      堆栈stack_1里的元素有:金牛
      堆栈stack_path要素有:老鼠
      访问的元素是:白虎
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3
      堆栈stack_1里的元素有:金牛、白虎
      堆栈stack_path要素有:老鼠、金牛
      访问的元素是:毒蛇
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4
      堆栈stack_1里的元素有:金牛、白虎、毒蛇
      堆栈stack_path要素有:老鼠、金牛、白虎
      访问的元素是:狡兔
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、狡兔
      堆栈stack_path要素有:老鼠、金牛、白虎、狡兔
      弹出堆栈stack_path要素:狡兔
      弹出堆栈stack_1要素:狡兔
      访问的元素是:笨猪
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、笨猪
      堆栈stack_path要素有:老鼠、金牛、白虎、狡兔
      访问的元素是:骏马
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、笨猪、骏马
      堆栈stack_path要素有:老鼠、金牛、白虎、狡兔、青龙
注意:骏马 的值为 7 大于金牛的值2
      弹出堆栈stack_path要素:骏马
      弹出堆栈stack_path要素:笨猪
      弹出堆栈stack_path要素:毒蛇
      弹出堆栈stack_path要素:白虎
      访问的元素是:青龙
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7、青龙=>8
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙
      堆栈stack_path要素有:老鼠、金牛
注意:青龙 的值为 8 大于笨猪的值6
      弹出堆栈stack_path要素:青龙
      访问的元素是:狗仔
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7、青龙=>8、狗仔=>9
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、狗仔
      堆栈stack_path要素有:老鼠、金牛
      弹出堆栈stack_path要素:狗仔
      弹出堆栈stack_1要素:狗仔
      访问的元素是:山鸡
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7、青龙=>8、狗仔=>9、山鸡=>10
      堆栈stack_1里的元素有:金牛、白虎、毒蛇、笨猪、骏马、青龙、山鸡
      堆栈stack_path要素有:老鼠、金牛
注意:山鸡 的值为 10 大于金牛的值2
      弹出堆栈stack_path要素:山鸡
      弹出堆栈stack_path要素:金牛
      弹出堆栈stack_1要素:山鸡
      弹出堆栈stack_1要素:青龙
      弹出堆栈stack_1要素:骏马
      弹出堆栈stack_1要素:笨猪
      弹出堆栈stack_1要素:毒蛇
      弹出堆栈stack_1要素:白虎
      弹出堆栈stack_1要素:金牛
      访问的元素是:小羊
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7、青龙=>8、狗仔=>9、山鸡=>10、小羊=>11
      堆栈stack_1里的元素有:小羊
      堆栈stack_path要素有:老鼠
      访问的元素是:猕猴
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、毒蛇=>4、狡兔=>5、笨猪=>6、骏马=>7、青龙=>8、狗仔=>9、山鸡=>10、小羊=>11、猕猴=>12
      堆栈stack_1里的元素有:小羊、猕猴
      堆栈stack_path要素有:老鼠、金牛
      弹出堆栈stack_path要素:猕猴
      弹出堆栈stack_1要素:猕猴
      弹出堆栈stack_path要素:小羊
      弹出堆栈stack_1要素:小羊

分别用kosaraju、Tarjan、Gabow计算出来后的着色变换矩阵


   小羊 猕猴 金牛 骏马 白虎 笨猪 青龙 毒蛇 山鸡 狗仔 狡兔 老鼠
小羊   1       1                     
猕猴                                   
金牛            1          1    1 1
骏马      1          1               
白虎         1          1            
笨猪         1                1      
青龙               1             1   
毒蛇               1             1   
山鸡      1                           
狗仔                                   
狡兔                                   
老鼠                                   
   老鼠 狡兔 狗仔 山鸡 青龙 骏马 笨猪 毒蛇 白虎 金牛 猕猴 小羊
老鼠                                   
狡兔                                   
狗仔                                   
山鸡                           1      
青龙   1             1               
骏马            1             1      
笨猪      1       1                  
毒蛇   1             1               
白虎               1    1            
金牛1 1    1             1         
猕猴                                   
小羊                        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层
老鼠要素
金牛要素
白虎要素
狡兔要素
青龙要素
毒蛇要素
骏马要素
小羊要素
猕猴要素
山鸡要素
狗仔要素
笨猪要素
第0层
第1层
第2层
第3层
第4层
第5层
老鼠要素
金牛要素
白虎要素
狡兔要素
青龙要素
毒蛇要素
骏马要素
小羊要素
猕猴要素
山鸡要素
狗仔要素
笨猪要素
第0层
第1层
第2层
第3层
第4层
第5层

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