利用kosaraju求强连通子集
论文写作或者计算需要帮助可发邮件到 hwstu # sohu.com 把 #替换成@，请说清来意，不必拐弯抹角，浪费相互之间的时间。
返回首页
此处输入要素的个数：
kosaraju(克鲁斯克尔)算法是用于求有向图的强连通分量的算法之一
时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。
这里没有把反图的时间算到里面。
步骤概要：
1. DFS有向图G，并以后根序记录节点
2. 把存在于记录集中且最后访问节点作为起点，DFS反图GT,并以先根序把节点从记录中剔除；
3. 若此次不能DFS反图GT所有节点，则重复步骤2，直到所有节点都被剔除出记录；每次剔除掉的节点集即为原有向图G的一个强连通分量
简要证明:
1. 第一次DFS有向图G时，最后记录下的节点必为最后一棵生成树的根节点。
证明：假设最后记录下节点不是树根，则必存在一节点为树根，且树根节点必为此节点祖先；而由后根序访问可知祖先节点比此节点更晚访问，矛盾；原命题成立
2. 第一次DFS的生成森林中，取两节点A、B，满足：B比A更晚记录下,且B不是A的祖先(即在第一次DFS中，A、B处于不同的生成树中)；则在第二次DFS的生成森林中，B不是A的祖先，且A也不是B的祖先(即在第二次DFS中，A、B处于不同的生成树中)。
证明：假设在第二次DFS的生成森林中，B是A的祖先，则反图GT中存在B到A路径，即第一次DFS生成森林中，A是B的祖先，则A必比B更晚记录下，矛盾；假设在第二次DFS的生成森林中，A是B的祖先，则反图GT中存在A到B路径，即第一次DFS生成森林中，B是A的祖先,矛盾；原命题成立
3. 按上述步骤求出的必为强连通分量
证明：首先，证明2保证了第二次DFS中的每一棵树都是第一次DFS中的某棵树或某棵树的子树。其次，对于第二次DFS中的每棵树，第一次DFS保证了从根到其子孙的连通性，第二次DFS保证了根到子孙的反向连通性(即子孙到根的连通性)；由此，此树中的每个节点都通过其根相互连通。
显示的是一个随机 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 |
|
|
1 |
| 笨猪 |
1 |
|
|
|
|
|
|
|
|
|
|
|
把元素：老鼠弹出->
; 回路0里的元素有：老鼠
; 回路0里的元素有：老鼠、毒蛇
; 回路0里的元素有：老鼠、毒蛇、狡兔
; 回路0里的元素有：老鼠、毒蛇、狡兔、青龙
; 回路0里的元素有：老鼠、毒蛇、狡兔、青龙、山鸡
; 回路0里的元素有：老鼠、毒蛇、狡兔、青龙、山鸡、猕猴
; 回路0里的元素有：老鼠、毒蛇、狡兔、青龙、山鸡、猕猴、狗仔
; 回路0里的元素有：老鼠、毒蛇、狡兔、青龙、山鸡、猕猴、狗仔、笨猪
回路序号1加一
把元素：笨猪弹出->
把元素：猕猴弹出->
把元素：狗仔弹出->
把元素：山鸡弹出->
把元素：狡兔弹出->
把元素：毒蛇弹出->
把元素：青龙弹出->
把元素：白虎弹出->
; 回路1里的元素有：白虎
回路序号2加一
把元素：小羊弹出->
; 回路2里的元素有：小羊
回路序号3加一
把元素：金牛弹出->
; 回路3里的元素有：金牛
回路序号4加一
把元素：骏马弹出->
; 回路4里的元素有：骏马
回路序号5加一
| |
老鼠 |
毒蛇 |
狡兔 |
青龙 |
山鸡 |
猕猴 |
狗仔 |
笨猪 |
白虎 |
小羊 |
金牛 |
骏马 |
| 老鼠 | |
|
|
|
|
|
|
1 |
|
|
|
1 |
|---|
| 毒蛇 | 1 |
|
|
|
|
|
|
|
|
|
1 |
|
|---|
| 狡兔 | |
1 |
|
1 |
|
|
|
|
1 |
|
|
1 |
|---|
| 青龙 | |
|
1 |
|
|
1 |
|
|
|
|
1 |
|
|---|
| 山鸡 | |
|
1 |
|
|
|
|
|
|
|
|
|
|---|
| 猕猴 | |
|
|
|
1 |
|
1 |
|
|
|
1 |
1 |
|---|
| 狗仔 | |
|
|
|
1 |
1 |
|
|
|
|
|
|
|---|
| 笨猪 | |
|
|
|
|
1 |
1 |
|
|
|
|
|
|---|
| 白虎 | |
|
|
|
|
|
|
|
|
1 |
|
|
|---|
| 小羊 | |
|
|
|
|
|
|
|
|
|
|
|
|---|
| 金牛 | |
|
|
|
|
|
|
|
|
|
|
|
|---|
| 骏马 | |
|
|
|
|
|
|
|
|
|
|
|
|---|
计算出来后的
化学加平台
解释结构模型
感谢化学加提供单独服务器服务器！请大家多支持化学加平台，可以多介绍人关注化学加！
对解释结构模型在线计算有什么意见与建议请发电子邮件到， hwstu #sohu.com 把#替换成 @