三种方法求强连通分量的比较
论文写作或者计算需要帮助可发邮件到 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 |
|
|
|
|
|
|
把元素：青龙弹出->
; 回路0里的元素有：青龙
回路序号1加一
把元素：老鼠弹出->
; 回路1里的元素有：老鼠
; 回路1里的元素有：老鼠、狡兔
; 回路1里的元素有：老鼠、狡兔、白虎
; 回路1里的元素有：老鼠、狡兔、白虎、骏马
; 回路1里的元素有：老鼠、狡兔、白虎、骏马、小羊
; 回路1里的元素有：老鼠、狡兔、白虎、骏马、小羊、猕猴
回路序号2加一
把元素：骏马弹出->
把元素：白虎弹出->
把元素：狡兔弹出->
把元素：猕猴弹出->
把元素：小羊弹出->
把元素：金牛弹出->
; 回路2里的元素有：金牛
; 回路2里的元素有：金牛、毒蛇
; 回路2里的元素有：金牛、毒蛇、狗仔
; 回路2里的元素有：金牛、毒蛇、狗仔、山鸡
回路序号3加一
把元素：山鸡弹出->
把元素：狗仔弹出->
把元素：毒蛇弹出->
把元素：笨猪弹出->
; 回路3里的元素有：笨猪
回路序号4加一
开始用深度搜索，从第一个节点开始！
访问的元素是：老鼠
堆栈里的元素有：老鼠
数组dfn中各个要素的值：老鼠=1
数组dfn中各个要素的值：老鼠=1
访问的元素是：金牛
堆栈里的元素有：老鼠、金牛
数组dfn中各个要素的值：老鼠=1、金牛=2
数组dfn中各个要素的值：老鼠=1、金牛=2
访问的元素是：毒蛇
堆栈里的元素有：老鼠、金牛、毒蛇
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3
要素金牛在dfn数组中的值，小于毒蛇在low数组中的值，现在进行赋值 low毒蛇=dfn金牛;
访问的元素是：笨猪
堆栈里的元素有：老鼠、金牛、毒蛇、笨猪
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4
此时笨猪在两个数组中的值相等，并且前驱节点为空！
堆栈里的元素有：老鼠、金牛、毒蛇、笨猪
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4
弹出要素笨猪 如果不等于笨猪继续弹出
堆栈里的元素有：老鼠、金牛、毒蛇
停止弹出！
访问的元素是：山鸡
堆栈里的元素有：老鼠、金牛、毒蛇、山鸡
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=5
访问的元素是：狗仔
堆栈里的元素有：老鼠、金牛、毒蛇、山鸡、狗仔
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=5、狗仔=6
要素毒蛇在dfn数组中的值，小于狗仔在low数组中的值，现在进行赋值 low狗仔=dfn毒蛇;
要素狗仔在low数组中的值，小于山鸡在low数组中的值，现在进行赋值让两个相等
此时金牛在两个数组中的值相等，并且前驱节点为空！
堆栈里的元素有：老鼠、金牛、毒蛇、山鸡、狗仔
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3
弹出要素狗仔 如果不等于金牛继续弹出
堆栈里的元素有：老鼠、金牛、毒蛇、山鸡
弹出要素山鸡 如果不等于金牛继续弹出
堆栈里的元素有：老鼠、金牛、毒蛇
弹出要素毒蛇 如果不等于金牛继续弹出
堆栈里的元素有：老鼠、金牛
弹出要素金牛 如果不等于金牛继续弹出
堆栈里的元素有：老鼠
停止弹出！
访问的元素是：骏马
堆栈里的元素有：老鼠、骏马
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=7
访问的元素是：白虎
堆栈里的元素有：老鼠、骏马、白虎
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=7、白虎=8
访问的元素是：狡兔
堆栈里的元素有：老鼠、骏马、白虎、狡兔
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=7、白虎=8、狡兔=9
要素老鼠在dfn数组中的值，小于狡兔在low数组中的值，现在进行赋值 low狡兔=dfn老鼠;
访问的元素是：猕猴
堆栈里的元素有：老鼠、骏马、白虎、狡兔、猕猴
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9、猕猴=10
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=7、白虎=8、狡兔=1、猕猴=10
要素白虎在dfn数组中的值，小于猕猴在low数组中的值，现在进行赋值 low猕猴=dfn白虎;
访问的元素是：小羊
堆栈里的元素有：老鼠、骏马、白虎、狡兔、猕猴、小羊
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9、猕猴=10、小羊=11
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=7、白虎=8、狡兔=1、猕猴=8、小羊=11
要素老鼠在dfn数组中的值，小于小羊在low数组中的值，现在进行赋值 low小羊=dfn老鼠;
要素小羊在low数组中的值，小于猕猴在low数组中的值，现在进行赋值让两个相等
要素狡兔在low数组中的值，小于白虎在low数组中的值，现在进行赋值让两个相等
要素白虎在low数组中的值，小于骏马在low数组中的值，现在进行赋值让两个相等
此时老鼠在两个数组中的值相等，并且前驱节点为空！
堆栈里的元素有：老鼠、骏马、白虎、狡兔、猕猴、小羊
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9、猕猴=10、小羊=11
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=1、白虎=1、狡兔=1、猕猴=1、小羊=1
弹出要素小羊 如果不等于老鼠继续弹出
堆栈里的元素有：老鼠、骏马、白虎、狡兔、猕猴
弹出要素猕猴 如果不等于老鼠继续弹出
堆栈里的元素有：老鼠、骏马、白虎、狡兔
弹出要素狡兔 如果不等于老鼠继续弹出
堆栈里的元素有：老鼠、骏马、白虎
弹出要素白虎 如果不等于老鼠继续弹出
堆栈里的元素有：老鼠、骏马
弹出要素骏马 如果不等于老鼠继续弹出
堆栈里的元素有：老鼠
弹出要素老鼠 如果不等于老鼠继续弹出
堆栈里的元素有：
停止弹出！
访问的元素是：青龙
堆栈里的元素有：青龙
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9、猕猴=10、小羊=11、青龙=12
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=1、白虎=1、狡兔=1、猕猴=1、小羊=1、青龙=12
此时青龙在两个数组中的值相等，并且前驱节点为空！
堆栈里的元素有：青龙
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=3、笨猪=4、山鸡=5、狗仔=6、骏马=7、白虎=8、狡兔=9、猕猴=10、小羊=11、青龙=12
数组dfn中各个要素的值：老鼠=1、金牛=2、毒蛇=2、笨猪=4、山鸡=3、狗仔=3、骏马=1、白虎=1、狡兔=1、猕猴=1、小羊=1、青龙=12
弹出要素青龙 如果不等于青龙继续弹出
堆栈里的元素有：
停止弹出！
开始用深度搜索，从第一个节点开始！
访问的元素是：老鼠
搜索树里的元素的顺序是：老鼠=>1
堆栈stack_1里的元素有：老鼠
堆栈stack_path要素有：老鼠
访问的元素是：金牛
搜索树里的元素的顺序是：老鼠=>1、金牛=>2
堆栈stack_1里的元素有：老鼠、金牛
堆栈stack_path要素有：老鼠、金牛
访问的元素是：毒蛇
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3
堆栈stack_1里的元素有：老鼠、金牛、毒蛇
堆栈stack_path要素有：老鼠、金牛、白虎
注意：毒蛇 的值为 3 大于金牛的值2
弹出堆栈stack_path要素：毒蛇
访问的元素是：笨猪
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4
堆栈stack_1里的元素有：老鼠、金牛、毒蛇、笨猪
堆栈stack_path要素有：老鼠、金牛、白虎
弹出堆栈stack_path要素：笨猪
弹出堆栈stack_1要素：笨猪
访问的元素是：山鸡
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5
堆栈stack_1里的元素有：老鼠、金牛、毒蛇、山鸡
堆栈stack_path要素有：老鼠、金牛、白虎
访问的元素是：狗仔
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6
堆栈stack_1里的元素有：老鼠、金牛、毒蛇、山鸡、狗仔
堆栈stack_path要素有：老鼠、金牛、白虎、狡兔
注意：狗仔 的值为 6 大于毒蛇的值3
弹出堆栈stack_path要素：狗仔
弹出堆栈stack_path要素：山鸡
弹出堆栈stack_path要素：金牛
弹出堆栈stack_1要素：狗仔
弹出堆栈stack_1要素：山鸡
弹出堆栈stack_1要素：毒蛇
弹出堆栈stack_1要素：金牛
访问的元素是：骏马
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7
堆栈stack_1里的元素有：老鼠、骏马
堆栈stack_path要素有：老鼠、金牛
访问的元素是：白虎
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7、白虎=>8
堆栈stack_1里的元素有：老鼠、骏马、白虎
堆栈stack_path要素有：老鼠、金牛、白虎
访问的元素是：狡兔
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7、白虎=>8、狡兔=>9
堆栈stack_1里的元素有：老鼠、骏马、白虎、狡兔
堆栈stack_path要素有：老鼠、金牛、白虎、狡兔
注意：狡兔 的值为 9 大于老鼠的值1
弹出堆栈stack_path要素：狡兔
弹出堆栈stack_path要素：白虎
弹出堆栈stack_path要素：骏马
访问的元素是：猕猴
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7、白虎=>8、狡兔=>9、猕猴=>10
堆栈stack_1里的元素有：老鼠、骏马、白虎、狡兔、猕猴
堆栈stack_path要素有：老鼠、金牛
注意：猕猴 的值为 10 大于白虎的值8
弹出堆栈stack_path要素：猕猴
访问的元素是：小羊
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7、白虎=>8、狡兔=>9、猕猴=>10、小羊=>11
堆栈stack_1里的元素有：老鼠、骏马、白虎、狡兔、猕猴、小羊
堆栈stack_path要素有：老鼠、金牛
注意：小羊 的值为 11 大于老鼠的值1
弹出堆栈stack_path要素：小羊
弹出堆栈stack_path要素：老鼠
弹出堆栈stack_1要素：小羊
弹出堆栈stack_1要素：猕猴
弹出堆栈stack_1要素：狡兔
弹出堆栈stack_1要素：白虎
弹出堆栈stack_1要素：骏马
弹出堆栈stack_1要素：老鼠
访问的元素是：青龙
搜索树里的元素的顺序是：老鼠=>1、金牛=>2、毒蛇=>3、笨猪=>4、山鸡=>5、狗仔=>6、骏马=>7、白虎=>8、狡兔=>9、猕猴=>10、小羊=>11、青龙=>12
堆栈stack_1里的元素有：青龙
堆栈stack_path要素有：老鼠
弹出堆栈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 |
|
|
|
|
|---|
计算出来后的
化学加平台
解释结构模型
感谢化学加提供单独服务器服务器！请大家多支持化学加平台，可以多介绍人关注化学加！
对解释结构模型在线计算有什么意见与建议请发电子邮件到， hwstu #sohu.com 把#替换成 @