快捷導(dǎo)航

Kosaraju算法詳解

更新時(shí)間：2017年09月09日 13:49:50 作者：zhangqi66

這篇文章主要為大家詳細(xì)介紹了Kosaraju算法，Kosaraju算法可以計(jì)算出一個(gè)有向圖的強(qiáng)連通分量，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

Kosaraju算法是干什么的？

Kosaraju算法可以計(jì)算出一個(gè)有向圖的強(qiáng)連通分量

什么是強(qiáng)連通分量？

在一個(gè)有向圖中如果兩個(gè)結(jié)點(diǎn)（結(jié)點(diǎn)v與結(jié)點(diǎn)w）在同一個(gè)環(huán)中（等價(jià)于v可通過(guò)有向路徑到達(dá)w，w也可以到達(dá)v）它們兩個(gè)就是強(qiáng)連通的，所有互為強(qiáng)連通的點(diǎn)組成了一個(gè)集合，在一幅有向圖中這種集合的數(shù)量就是這幅圖的強(qiáng)連通分量的數(shù)量

怎么算？？

第一步：計(jì)算出有向圖 (G) 的反向圖 (G反) 的逆后序排列（代碼中有介紹）

第二步：在有向圖 (G) 中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索，按照剛才計(jì)算出的逆后序排列順序而非標(biāo)準(zhǔn)順序

class Kosaraju {
  private Digraph G;
  private Digraph reverseG; //反向圖
  private Stack<Integer> reversePost; //逆后續(xù)排列保存在這
  private boolean[] marked;
  private int[] id; //第v個(gè)點(diǎn)在幾個(gè)強(qiáng)連通分量中
  private int count; //強(qiáng)連通分量的數(shù)量
  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(); //算出逆后續(xù)排列
    
    for (int i = 0; i < marked.length; i++) { //重置標(biāo)記
      marked[i] = false;
    }
    
    for (int i = 0; i < G.V(); i++) { //算出強(qiáng)連通分量
      temp = reversePost.pop();
      if (!marked[temp]) {
        count++;
        dfs(temp);
      }
    }
  }
  /*
   * 下面兩個(gè)函數(shù)是為了算出 逆后序排列
   */
  private void makeReverPost() {
    for (int i = 0; i < G.V(); i++) { //V()返回的是圖G的節(jié)點(diǎn)數(shù)
      if (!marked[i])
        redfs(i);
    }
  }
  
  private void redfs(int v) {
    marked[v] = true;
    for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的結(jié)點(diǎn)的集合
      if (!marked[w])
        redfs(w);
    }
    reversePost.push(v); //在這里把v加入棧,完了到時(shí)候再?gòu)棾鰜?lái),彈出來(lái)的就是逆后續(xù)排列
  }
  /*
   * 標(biāo)準(zhǔn)的深度優(yōu)先搜索
   */
  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;}
}

為什么這樣就可以算出強(qiáng)連通分量的數(shù)量？（稍微有些費(fèi)解）

比如有這樣一個(gè)圖，它有五個(gè)強(qiáng)連通分量

我們需要證明在26行的dfs(temp)中找到的①全是點(diǎn)temp的強(qiáng)連通點(diǎn)，②且是它全部的強(qiáng)連通點(diǎn)

證明時(shí)不要忘了定義：v可通過(guò)有向路徑到達(dá)w，w也可以到達(dá)v，則它倆強(qiáng)連通

先證明②：

用反證法，就假如對(duì)一個(gè)點(diǎn)（點(diǎn)w）深度優(yōu)先搜索時(shí)有一個(gè)它的強(qiáng)連通點(diǎn)（點(diǎn)v）沒(méi)找到。

如果沒(méi)找到，那就說(shuō)明點(diǎn)v 已經(jīng)在找其他點(diǎn)時(shí)標(biāo)記過(guò)了，但點(diǎn)v 如果已經(jīng)被標(biāo)記過(guò)了，因?yàn)橛幸粭l v -> w 的有向路徑，那點(diǎn)w 肯定也被找過(guò)了，那就不會(huì)對(duì) 點(diǎn)w 深度優(yōu)先搜索了。

假設(shè)不成立 (*^ω^*)

再證明①：

對(duì)一個(gè)點(diǎn)（點(diǎn)w）深度優(yōu)先搜索時(shí)找到了一個(gè)點(diǎn)（點(diǎn)v），說(shuō)明有一條 w -> v 的有向路徑，再證明有一條 v -> w 的路徑就行了，證明有一條 v -> w 的路徑，就相當(dāng)于證明圖G的反向圖（G反）有一條 w -> v 的有向路徑，因?yàn)?點(diǎn)w 和點(diǎn)v 滿(mǎn)足那個(gè) 逆后序排列，而逆后序排列是在redfs(node)結(jié)束時(shí)將node加入棧，再?gòu)臈Ｖ袕棾?，那說(shuō)明反向圖的深度優(yōu)先搜索中redfs(v)肯定在redfs(w)前就結(jié)束了，那就是兩種情況：

■ redfs(v)已經(jīng)完了redfs(w)才開(kāi)始

■ redfs(v)是在 redfs(w)開(kāi)始之后結(jié)束之前結(jié)束的，也就是redfs(v)是在redfs(w)內(nèi)部結(jié)束的

第一種情況不可能，因?yàn)?G反有一條 v -> w 的路徑（因?yàn)镚有一條 w -> v 的路徑），滿(mǎn)足第二中情況即在 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; //逆后續(xù)排列保存在這
  private boolean[] marked;
  private int[] id; //第v個(gè)點(diǎn)在幾個(gè)強(qiáng)連通分量中
  private int count; //強(qiáng)連通分量的數(shù)量
  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(); //算出逆后續(xù)排列
    
    for (int i = 0; i < marked.length; i++) { //重置標(biāo)記
      marked[i] = false;
    }
    
    for (int i = 0; i < G.V(); i++) { //算出強(qiáng)連通分量
      temp = reversePost.pop();
      if (!marked[temp]) {
        count++;
        dfs(temp);
      }
    }
  }
  /*
   * 下面兩個(gè)函數(shù)是為了算出 逆后序排列
   */
  private void makeReverPost() {
    for (int i = 0; i < G.V(); i++) { //V()返回的是圖G的節(jié)點(diǎn)數(shù)
      if (!marked[i])
        redfs(i);
    }
  }
  
  private void redfs(int v) {
    marked[v] = true;
    for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的結(jié)點(diǎn)的集合
      if (!marked[w])
        redfs(w);
    }
    reversePost.push(v); //在這里把v加入棧,完了到時(shí)候再?gòu)棾鰜?lái),彈出來(lái)的就是逆后續(xù)排列
  }
  /*
   * 標(biāo)準(zhǔn)的深度優(yōu)先搜索
   */
  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;}

}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: