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


论文写作或者计算需要帮助可发邮件到 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 1    1                  
狗仔             1             1      
笨猪                1          1      
  把元素:青龙弹出->
     ; 回路0里的元素有:青龙
  回路序号1加一
  把元素:猕猴弹出->
     ; 回路1里的元素有:猕猴
  回路序号2加一
  把元素:骏马弹出->
     ; 回路2里的元素有:骏马
  回路序号3加一
  把元素:狡兔弹出->
     ; 回路3里的元素有:狡兔
  回路序号4加一
  把元素:白虎弹出->
     ; 回路4里的元素有:白虎
  回路序号5加一
  把元素:山鸡弹出->
     ; 回路5里的元素有:山鸡
     ; 回路5里的元素有:山鸡、毒蛇
  回路序号6加一
  把元素:狗仔弹出->
     ; 回路6里的元素有:狗仔
  回路序号7加一
  把元素:毒蛇弹出->
  把元素:笨猪弹出->
     ; 回路7里的元素有:笨猪
  回路序号8加一
  把元素:小羊弹出->
     ; 回路8里的元素有:小羊
  回路序号9加一
  把元素:金牛弹出->
     ; 回路9里的元素有:金牛
  回路序号10加一
  把元素:老鼠弹出->
     ; 回路10里的元素有:老鼠
  回路序号11加一
  开始用深度搜索,从第一个节点开始!
      访问的元素是:老鼠
      堆栈里的元素有:老鼠
      数组dfn中各个要素的值:老鼠=1
      数组dfn中各个要素的值:老鼠=1
          此时老鼠在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:老鼠
        数组dfn中各个要素的值:老鼠=1
        数组dfn中各个要素的值:老鼠=1
          弹出要素老鼠 如果不等于老鼠继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:金牛
      堆栈里的元素有:金牛
      数组dfn中各个要素的值:老鼠=1、金牛=2
      数组dfn中各个要素的值:老鼠=1、金牛=2
          此时金牛在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:金牛
        数组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数组中的值,小于毒蛇在low数组中的值,现在进行赋值 low毒蛇=dfn山鸡;
      访问的元素是:笨猪
      堆栈里的元素有:白虎、山鸡、毒蛇、笨猪
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6
      访问的元素是:小羊
      堆栈里的元素有:白虎、山鸡、毒蛇、笨猪、小羊
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7
          此时小羊在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:白虎、山鸡、毒蛇、笨猪、小羊
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7
          弹出要素小羊 如果不等于小羊继续弹出
         堆栈里的元素有:白虎、山鸡、毒蛇、笨猪
          停止弹出!
          此时笨猪在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:白虎、山鸡、毒蛇、笨猪
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7
          弹出要素笨猪 如果不等于笨猪继续弹出
         堆栈里的元素有:白虎、山鸡、毒蛇
          停止弹出!
      访问的元素是:狗仔
      堆栈里的元素有:白虎、山鸡、毒蛇、狗仔
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8
          此时狗仔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:白虎、山鸡、毒蛇、狗仔
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8
          弹出要素狗仔 如果不等于狗仔继续弹出
         堆栈里的元素有:白虎、山鸡、毒蛇
          停止弹出!
          此时山鸡在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:白虎、山鸡、毒蛇
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8
          弹出要素毒蛇 如果不等于山鸡继续弹出
         堆栈里的元素有:白虎、山鸡
          弹出要素山鸡 如果不等于山鸡继续弹出
         堆栈里的元素有:白虎
          停止弹出!
          此时白虎在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:白虎
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8
          弹出要素白虎 如果不等于白虎继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:狡兔
      堆栈里的元素有:狡兔
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9
          此时狡兔在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:狡兔
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9
          弹出要素狡兔 如果不等于狡兔继续弹出
         堆栈里的元素有:
          停止弹出!
      访问的元素是:青龙
      堆栈里的元素有:青龙
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10
      访问的元素是:猕猴
      堆栈里的元素有:青龙、猕猴
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11
      访问的元素是:骏马
      堆栈里的元素有:青龙、猕猴、骏马
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
      数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
          此时骏马在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:青龙、猕猴、骏马
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
          弹出要素骏马 如果不等于骏马继续弹出
         堆栈里的元素有:青龙、猕猴
          停止弹出!
          此时猕猴在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:青龙、猕猴
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
          弹出要素猕猴 如果不等于猕猴继续弹出
         堆栈里的元素有:青龙
          停止弹出!
          此时青龙在两个数组中的值相等,并且前驱节点为空!
         堆栈里的元素有:青龙
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=5、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
        数组dfn中各个要素的值:老鼠=1、金牛=2、白虎=3、山鸡=4、毒蛇=4、笨猪=6、小羊=7、狗仔=8、狡兔=9、青龙=10、猕猴=11、骏马=12
          弹出要素青龙 如果不等于青龙继续弹出
         堆栈里的元素有:
          停止弹出!
  开始用深度搜索,从第一个节点开始!
      访问的元素是:老鼠
      搜索树里的元素的顺序是:老鼠=>1
      堆栈stack_1里的元素有:老鼠
      堆栈stack_path要素有:老鼠
      弹出堆栈stack_path要素:老鼠
      弹出堆栈stack_1要素:老鼠
      访问的元素是:金牛
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2
      堆栈stack_1里的元素有:金牛
      堆栈stack_path要素有:老鼠
      弹出堆栈stack_path要素:金牛
      弹出堆栈stack_1要素:金牛
      访问的元素是:白虎
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3
      堆栈stack_1里的元素有:白虎
      堆栈stack_path要素有:老鼠
      访问的元素是:山鸡
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、山鸡=>4
      堆栈stack_1里的元素有:白虎、山鸡
      堆栈stack_path要素有:老鼠、金牛
      访问的元素是:毒蛇
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、山鸡=>4、毒蛇=>5
      堆栈stack_1里的元素有:白虎、山鸡、毒蛇
      堆栈stack_path要素有:老鼠、金牛、白虎
注意:毒蛇 的值为 5 大于山鸡的值4
      弹出堆栈stack_path要素:毒蛇
      访问的元素是:笨猪
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、山鸡=>4、毒蛇=>5、笨猪=>6
      堆栈stack_1里的元素有:白虎、山鸡、毒蛇、笨猪
      堆栈stack_path要素有:老鼠、金牛、白虎
      访问的元素是:小羊
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、山鸡=>4、毒蛇=>5、笨猪=>6、小羊=>7
      堆栈stack_1里的元素有:白虎、山鸡、毒蛇、笨猪、小羊
      堆栈stack_path要素有:老鼠、金牛、白虎、狡兔
      弹出堆栈stack_path要素:小羊
      弹出堆栈stack_1要素:小羊
      弹出堆栈stack_path要素:笨猪
      弹出堆栈stack_1要素:笨猪
      访问的元素是:狗仔
      搜索树里的元素的顺序是:老鼠=>1、金牛=>2、白虎=>3、山鸡=>4、毒蛇=>5、笨猪=>6、小羊=>7、狗仔=>8
      堆栈stack_1里的元素有:白虎、山鸡、毒蛇、狗仔
      堆栈stack_path要素有:老鼠、金牛、白虎
      弹出堆栈stack_path要素:狗仔
      弹出堆栈stack_1要素:狗仔
      弹出堆栈stack_path要素:山鸡
      弹出堆栈stack_1要素:毒蛇
      弹出堆栈stack_1要素:山鸡
      弹出堆栈stack_path要素:白虎
      弹出堆栈stack_1要素:白虎
      访问的元素是:狡兔
      搜索树里的元素的顺序是:老鼠=>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要素有:老鼠
      访问的元素是:猕猴
      搜索树里的元素的顺序是:老鼠=>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要素:猕猴
      弹出堆栈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               
骏马                                   
猕猴   1          1          1      
青龙   1 1    1 1       1    1   

计算出来后的


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

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