利用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里的元素有:金牛、白虎、毒蛇、骏马、狡兔
     ; 回路2里的元素有:金牛、白虎、毒蛇、骏马、狡兔、山鸡
     ; 回路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         
笨猪                                   
老鼠                                   

计算出来后的


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

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