Kosaraju算法詳解
Kosaraju算法是干什么的？
Kosaraju算法可以計算出一個有向圖的強(qiáng)連通分量
什么是強(qiáng)連通分量？
在一個有向圖中如果兩個結(jié)點（結(jié)點v與結(jié)點w）在同一個環(huán)中（等價于v可通過有向路徑到達(dá)w，w也可以到達(dá)v）它們兩個就是強(qiáng)連通的，所有互為強(qiáng)連通的點組成了一個集合，在一幅有向圖中這種集合的數(shù)量就是這幅圖的強(qiáng)連通分量的數(shù)量
怎么算？？
第一步：計算出有向圖 (G) 的反向圖 (G反) 的逆后序排列（代碼中有介紹）
第二步：在有向圖 (G) 中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索，按照剛才計算出的逆后序排列順序而非標(biāo)準(zhǔn)順序
class Kosaraju {
private Digraph G;
private Digraph reverseG; //反向圖
private Stack<Integer> reversePost; //逆后續(xù)排列保存在這
private boolean[] marked;
private int[] id; //第v個點在幾個強(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);
}
}
}
/*
* 下面兩個函數(shù)是為了算出 逆后序排列
*/
private void makeReverPost() {
for (int i = 0; i < G.V(); i++) { //V()返回的是圖G的節(jié)點數(shù)
if (!marked[i])
redfs(i);
}
}
private void redfs(int v) {
marked[v] = true;
for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的結(jié)點的集合
if (!marked[w])
redfs(w);
}
reversePost.push(v); //在這里把v加入棧,完了到時候再彈出來,彈出來的就是逆后續(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ù)量？（稍微有些費解）
比如有這樣一個圖，它有五個強(qiáng)連通分量
我們需要證明在26行的dfs(temp)中找到的①全是點temp的強(qiáng)連通點，②且是它全部的強(qiáng)連通點
證明時不要忘了定義：v可通過有向路徑到達(dá)w，w也可以到達(dá)v，則它倆強(qiáng)連通
先證明②：
用反證法，就假如對一個點（點w）深度優(yōu)先搜索時有一個它的強(qiáng)連通點（點v）沒找到。
如果沒找到，那就說明 點v 已經(jīng)在找其他點時標(biāo)記過了， 但 點v 如果已經(jīng)被標(biāo)記過了，因為有一條 v -> w 的有向路徑，那 點w 肯定也被找過了，那就不會對 點w 深度優(yōu)先搜索了。
假設(shè)不成立 (*^ω^*)
再證明①：
對一個點（點w）深度優(yōu)先搜索時找到了一個點（點v），說明有一條 w -> v 的有向路徑，再證明有一條 v -> w 的路徑就行了，證明有一條 v -> w 的路徑，就相當(dāng)于證明圖G的反向圖（G反）有一條 w -> v 的有向路徑，因為 點w 和 點v 滿足那個 逆后序排列，而逆后序排列是在redfs(node)結(jié)束時將node加入棧，再從棧中彈出，那說明反向圖的深度優(yōu)先搜索中redfs(v)肯定在redfs(w)前就結(jié)束了，那就是兩種情況：
■ redfs(v)已經(jīng)完了redfs(w)才開始
■ redfs(v)是在 redfs(w)開始之后結(jié)束之前 結(jié)束的，也就是redfs(v)是在redfs(w)內(nèi)部結(jié)束的
第一種情況不可能，因為 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; //逆后續(xù)排列保存在這
private boolean[] marked;
private int[] id; //第v個點在幾個強(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);
}
}
}
/*
* 下面兩個函數(shù)是為了算出 逆后序排列
*/
private void makeReverPost() {
for (int i = 0; i < G.V(); i++) { //V()返回的是圖G的節(jié)點數(shù)
if (!marked[i])
redfs(i);
}
}
private void redfs(int v) {
marked[v] = true;
for (Integer w: reverseG.adj(v)) { //adj(v)返回的是v指向的結(jié)點的集合
if (!marked[w])
redfs(w);
}
reversePost.push(v); //在這里把v加入棧,完了到時候再彈出來,彈出來的就是逆后續(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;}
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要詳細(xì)介紹了SpringBoot訪問HTML的全過程，文章中有詳細(xì)的代碼和圖片講解，感興趣的同學(xué)可以參考一下2023-04-04
java實現(xiàn)一個接口調(diào)取另一個接口(接口一調(diào)取接口二)
這篇文章主要介紹了java實現(xiàn)一個接口調(diào)取另一個接口(接口一調(diào)取接口二)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了Java 設(shè)計模式原則之迪米特法則詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了Java探索之Thread+IO文件的加密解密代碼實例，具有一定參考價值，需要的朋友可以了解下。2017-10-10
Java Collection和Collections的區(qū)別
本文主要介紹了Java Collection和Collections的區(qū)別,Collection?是表示集合的接口,而?Collections?是對集合進(jìn)行操作的工具類,下面就來介紹一下具體用法,感興趣的可以了解一下2023-12-12
Java?spring?MVC環(huán)境中實現(xiàn)WebSocket的示例代碼
這篇文章主要介紹了Java?spring?MVC環(huán)境中實現(xiàn)WebSocket,本文通過示例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-09-09
SpringBoot項目中jar發(fā)布獲取jar包所在目錄路徑的最佳方法
在開發(fā)過程中,我們經(jīng)常要遇到上傳圖片、word、pdf等功能,但是當(dāng)我們把項目打包發(fā)布到服務(wù)器上時,對應(yīng)的很多存儲路徑的方法就會失效,下面這篇文章主要給大家介紹了關(guān)于SpringBoot項目中jar發(fā)布獲取jar包所在目錄路徑的相關(guān)資料2022-07-07
這篇文章主要為大家介紹了JDK8新出Optional類的發(fā)方法示例探索與思考分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-08-08
這篇文章主要介紹了Jsoup如何解析一個HTML文檔、從文件加載文檔、從URL加載Document等方法，對Jsoup常用方法做了詳細(xì)講解，最近提供了一個示例供大家參考 使用DOM方法來遍歷一個文檔 從元素抽取屬性，文本和HTML 獲取所有鏈接2013-11-11
本文主要介紹了Spring中的Environment外部化配置管理，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02