欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Kosaraju算法详解

程序员文章站 2024-02-26 22:45:22
kosaraju算法是干什么的? kosaraju算法可以计算出一个有向图的强连通分量 什么是强连通分量? 在一个有向图中如果两个结点(结点v与结点w)在同一个环中(...

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;}
}

为什么这样就可以算出强连通分量的数量?(稍微有些费解)

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

Kosaraju算法详解

 我们需要证明在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;}

}

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