Kosaraju算法详解

Kosaraju算法是干什么的？

Kosaraju算法可以计算出一个有向图的强连通分量

什么是强连通分量？

在一个有向图中如果两个结点（结点v与结点w）在同一个环中（等价于v可通过有向路径到达w，w也可以到达v）它们两个就是强连通的，所有互为强连通的点组成了一个集合，在一幅有向图中这种集合的数量就是这幅图的强连通分量的数量

怎么算？？

第一步：计算出有向图 (G) 的反向图 (G反) 的逆后序排列（代码中有介绍）

第二步：在有向图 (G) 中进行标准的深度优先搜索，按照刚才计算出的逆后序排列顺序而非标准顺序

class Kosaraju {
  private Digraph G;
  private Digraph reverseG; //反向图
  private Stack<Integer> reversePost; //逆后续排列保存在这
  private boolean[] marked;
  private int[] id; //第v个点在几个强连通分量中
  private int count; //强连通分量的数量
  public Kosaraju(Digraph G) {
    int temp;
    this.G = G;
    reverseG = G.reverse();
    marked   = new boolean[G.V()];
    id     = new int[G.V()];
    reversePost = new Stack<Integer>();
    
    makeReverPost(); //算出逆后续排列
    
    for (int i = 0; i < marked.length; i++) { //重置标记
      marked[i] = false;
    }
    
    for (int i = 0; i < G.V(); i++) { //算出强连通分量
      temp = reversePost.pop();
      if (!marked[temp]) {
        count++;
        dfs(temp);
      }
    }
  }
  /*
   * 下面两个函数是为了算出 逆后序排列
   */
  private void makeReverPost() {
    for (int i = 0; i < G.V(); i++) { //V()返回的是图G的节点数
      if (!marked[i])
        redfs(i);
    }
  }
  
  private void redfs(int v) {
    marked[v] = true;
    for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的结点的集合
      if (!marked[w])
        redfs(w);
    }
    reversePost.push(v); //在这里把v加入栈,完了到时候再弹出来,弹出来的就是逆后续排列
  }
  /*
   * 标准的深度优先搜索
   */
  private void dfs(int v) {
    marked[v] = true;
    id[v] = count;
    for (Integer w: G.adj(v)) {
      if (!marked[w])
        dfs(w);
    }
  }
  
  public int count() { return count;}
}

为什么这样就可以算出强连通分量的数量？（稍微有些费解）

比如有这样一个图，它有五个强连通分量

 我们需要证明在26行的dfs(temp)中找到的①全是点temp的强连通点，②且是它全部的强连通点

 证明时不要忘了定义：v可通过有向路径到达w，w也可以到达v，则它俩强连通 

 先证明②：

用反证法，就假如对一个点（点w）深度优先搜索时有一个它的强连通点（点v）没找到。

如果没找到，那就说明 点v 已经在找其他点时标记过了， 但 点v 如果已经被标记过了，因为有一条 v  -> w 的有向路径，那 点w 肯定也被找过了，那就不会对 点w 深度优先搜索了。

假设不成立     (*^ω^*)

 再证明①：

 对一个点（点w）深度优先搜索时找到了一个点（点v），说明有一条 w -> v 的有向路径，再证明有一条 v -> w 的路径就行了，证明有一条 v -> w 的路径，就相当于证明图G的反向图（G反）有一条 w -> v 的有向路径，因为 点w 和 点v 满足那个 逆后序排列，而逆后序排列是在redfs(node)结束时将node加入栈，再从栈中弹出，那说明反向图的深度优先搜索中redfs(v)肯定在redfs(w)前就结束了，那就是两种情况：

■ redfs(v)已经完了redfs(w)才开始

■ redfs(v)是在 redfs(w)开始之后结束之前 结束的，也就是redfs(v)是在redfs(w)内部结束的

第一种情况不可能，因为 G反 有一条 v -> w 的路径（因为G有一条 w -> v 的路径），满足第二中情况即在 G反 中有一条 w -> v 的路径。

终于证完了。

完整代码：

package practice;

import java.util.ArrayList;
import java.util.Stack;

public class TestMain {
  public static void main(String[] args) {
    Digraph a = new Digraph(13);
    a.addEdge(0, 1);a.addEdge(0, 5);a.addEdge(2, 3);a.addEdge(2, 0);a.addEdge(3, 2);
    a.addEdge(3, 5);a.addEdge(4, 3);a.addEdge(4, 2);a.addEdge(5, 4);a.addEdge(6, 0);
    a.addEdge(6, 4);a.addEdge(6, 9);a.addEdge(7, 6);a.addEdge(7, 8);a.addEdge(8, 7);
    a.addEdge(8, 9);a.addEdge(9, 10);a.addEdge(9, 11);a.addEdge(10, 12);a.addEdge(11, 4);
    a.addEdge(11, 12);a.addEdge(12, 9);
    
    Kosaraju b = new Kosaraju(a);
    System.out.println(b.count());
  }
}

class Kosaraju {
  private Digraph G;
  private Digraph reverseG; //反向图
  private Stack<Integer> reversePost; //逆后续排列保存在这
  private boolean[] marked;
  private int[] id; //第v个点在几个强连通分量中
  private int count; //强连通分量的数量
  public Kosaraju(Digraph G) {
    int temp;
    this.G = G;
    reverseG = G.reverse();
    marked   = new boolean[G.V()];
    id     = new int[G.V()];
    reversePost = new Stack<Integer>();
    
    makeReverPost(); //算出逆后续排列
    
    for (int i = 0; i < marked.length; i++) { //重置标记
      marked[i] = false;
    }
    
    for (int i = 0; i < G.V(); i++) { //算出强连通分量
      temp = reversePost.pop();
      if (!marked[temp]) {
        count++;
        dfs(temp);
      }
    }
  }
  /*
   * 下面两个函数是为了算出 逆后序排列
   */
  private void makeReverPost() {
    for (int i = 0; i < G.V(); i++) { //V()返回的是图G的节点数
      if (!marked[i])
        redfs(i);
    }
  }
  
  private void redfs(int v) {
    marked[v] = true;
    for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的结点的集合
      if (!marked[w])
        redfs(w);
    }
    reversePost.push(v); //在这里把v加入栈,完了到时候再弹出来,弹出来的就是逆后续排列
  }
  /*
   * 标准的深度优先搜索
   */
  private void dfs(int v) {
    marked[v] = true;
    id[v] = count;
    for (Integer w: G.adj(v)) {
      if (!marked[w])
        dfs(w);
    }
  }
  
  public int count() { return count;}
}
/*
 * 图
 */
class Digraph {
  private ArrayList<Integer>[] node;
  private int v;
  public Digraph(int v) {
    node = (ArrayList<Integer>[]) new ArrayList[v];
    for (int i = 0; i < v; i++)
      node[i] = new ArrayList<Integer>();
    this.v = v;
  }
  
  public void addEdge(int v, int w) { node[v].add(w);}
  
  public Iterable<Integer> adj(int v) { return node[v];}
  
  public Digraph reverse() {
    Digraph result = new Digraph(v);
    for (int i = 0; i < v; i++) {
      for (Integer w : adj(i))
        result.addEdge(w, i);
    }
    return result;
  }
  
  public int V() { return v;}

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# Kosaraju  # 算法  # 分享Java常用几种加密算法(四种)  # 关于各种排列组合java算法实现方法  # java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述  # java冒泡排序算法代码  # java实现MD5加密算法的实例代码  # 史上最全的java随机数生成算法分享  # 使用java自带des加密算法实现文件加密和字符串加密  # 用java实现冒泡排序算法  # 基于Java实现的Dijkstra算法示例  # java异或加密算法  # 的是  # 弹出  # 是在  # 过了  # 几个  # 在这里  # 计算出  # 那就  # 在这  # 中有  # 到时候  # 可通过  # 图中  # 是为了  # 环中  # 有一  # 不可能  # 如有  # 两种  # 这样一个 

相关文章： 如何安全更换建站之星模板并保留数据？  建站主机如何安装配置？新手必看操作指南  如何在Golang中指定模块版本_使用go.mod控制版本号  合肥做个网站多少钱,合肥本地有没有比较靠谱的交友平台？  怎么将XML数据可视化 D3.js加载XML  建站之星如何助力企业快速打造五合一网站？  北京网页设计制作网站有哪些,继续教育自动播放怎么设置？  如何用PHP快速搭建CMS系统？  郑州企业网站制作公司,郑州招聘网站有哪些？  深圳网站制作案例,网页的相关名词有哪些？  建站之星后台管理：高效配置与模板优化提升用户体验  成都响应式网站开发,dw怎么把手机适应页面变成网页？  北京营销型网站制作公司,可以用python做一个营销推广网站吗？  网站建设制作需要多少钱费用,自己做一个网站要多少钱，模板一般多少钱？  专业公司网站制作公司,用什么语言做企业网站比较好？  网站设计制作企业有哪些,抖音官网主页怎么设置？  开心动漫网站制作软件下载,十分开心动画为何停播？  如何快速搭建FTP站点实现文件共享？  如何用腾讯建站主机快速创建免费网站？  定制建站流程解析：需求评估与SEO优化功能开发指南  如何在建站宝盒中设置产品搜索功能？  高端建站三要素：定制模板、企业官网与响应式设计优化  C#如何在一个XML文件中查找并替换文本内容  贸易公司网站制作流程,出口贸易网站设计怎么做？  免费制作海报的网站,哪位做平面的朋友告诉我用什么软件做海报比较好?ps还是cd还是ai这几个软件我都会些我是做网页的？  建站之星各版本价格是多少？  公众号网站制作网页,微信公众号怎么制作？  湖州网站制作公司有哪些,浙江中蓝新能源公司官网？  免费网站制作appp,免费制作app哪个平台好？  如何用wdcp快速搭建高效网站？  电商网站制作公司有哪些,1688网是什么意思？  公司门户网站制作流程,华为官网怎么做？  如何在IIS管理器中快速创建并配置网站？  建站主机选哪家性价比最高？  如何在万网自助建站平台快速创建网站？  道歉网站制作流程,世纪佳缘致歉小吴事件，相亲网站身份信息伪造该如何稽查？  公司网站建设制作费用,想建设一个属于自己的企业网站，该如何去做？  网站制作外包价格怎么算,招聘网站上写的“外包”是什么意思？  免费ppt制作网站,有没有值得推荐的免费PPT网站？  开封网站制作公司,网络用语开封是什么意思？  教学网站制作软件,学习*后期制作的网站有哪些？  如何在Golang中使用encoding/gob序列化对象_存储和传输数据  制作网站的公司有哪些,做一个公司网站要多少钱？  ppt制作免费网站有哪些,ppt模板免费下载网站？  如何在万网自助建站中设置域名及备案？  电商平台网站制作流程,电商网站如何制作？  ui设计制作网站有哪些,手机UI设计网址吗？  建站之星2.7模板：企业网站建设与h5定制设计专题  网页制作模板网站推荐,网页设计海报之类的素材哪里好？  如何在云主机上快速搭建多站点网站？