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