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

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