利用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      
  把元素:山鸡弹出->
     ; 回路0里的元素有:山鸡
  回路序号1加一
  把元素:猕猴弹出->
     ; 回路1里的元素有:猕猴
  回路序号2加一
  把元素:金牛弹出->
     ; 回路2里的元素有:金牛
     ; 回路2里的元素有:金牛、青龙
     ; 回路2里的元素有:金牛、青龙、白虎
     ; 回路2里的元素有:金牛、青龙、白虎、毒蛇
     ; 回路2里的元素有:金牛、青龙、白虎、毒蛇、笨猪
  回路序号3加一
  把元素:笨猪弹出->
  把元素:毒蛇弹出->
  把元素:白虎弹出->
  把元素:青龙弹出->
  把元素:狡兔弹出->
     ; 回路3里的元素有:狡兔
  回路序号4加一
  把元素:老鼠弹出->
     ; 回路4里的元素有:老鼠
  回路序号5加一
  把元素:狗仔弹出->
     ; 回路5里的元素有:狗仔
  回路序号6加一
  把元素:小羊弹出->
     ; 回路6里的元素有:小羊
  回路序号7加一
  把元素:骏马弹出->
     ; 回路7里的元素有:骏马
  回路序号8加一
   山鸡 猕猴 金牛 青龙 白虎 毒蛇 笨猪 狡兔 老鼠 狗仔 小羊 骏马
山鸡                  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层

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