1、基本定義： 圖G(V,E)中，在深度搜索時為每一個節(jié)點(diǎn)記錄兩個時間戳，分別是開始掃描的時間d和將其所有子節(jié)點(diǎn)全部掃描完的時間f； 定義d(U)為節(jié)點(diǎn)集U中d的最小值，定義f(U)為節(jié)點(diǎn)集U中f的最大值。基本步驟： 1.對圖G進(jìn)行深度優(yōu)先搜索，記錄每個節(jié)點(diǎn)的d,f; 2.求圖G的轉(zhuǎn)置Gt（所有節(jié)點(diǎn)不變，邊的方向變反）; 3.按照步驟一所求的節(jié)點(diǎn)的f，按照降序，對Gt進(jìn)行深度優(yōu)先搜索，得到的深度優(yōu)先森林，森林中深度為1所形成的每個樹，即為各個強(qiáng)連通分量具體代碼：import java.util.ArrayList;import java.util.

2、LinkedList;import java.util.Scanner;/* * * author Founder * 通過深度優(yōu)先搜索，查找強(qiáng)連通分量 */public class Main static int time = 0; /時間戳 static ArrayList<Integer> topology; /記錄第一次搜索結(jié)果的拓?fù)渑判?public static void main(String args) /* * 輸入方式： * 第一行輸入節(jié)點(diǎn)的個數(shù)n * 后面n行輸入第n個節(jié)點(diǎn)（從0開始數(shù)）鏈接的子節(jié)點(diǎn)，沒有子節(jié)點(diǎn)則直接換行 */ Scanner input =

3、new Scanner(System.in); int n = input.nextInt(); Node nodes = new Noden; topology = new ArrayList<>(); for(int i = 0; i < n; +i) nodesi = new Node(); input.nextLine(); for(int i = 0; i < n; +i) String line = input.nextLine(); if(!line.equals("") String tempIntStr = line.split(&

4、quot; "); for(int j = 0; j < tempIntStr.length; +j) nodesi.addLinkNodes(Integer.parseInt(tempIntStrj); dfs(nodes); /* * 準(zhǔn)備第二次深度優(yōu)先搜索，先構(gòu)造轉(zhuǎn)置圖 */ Node secondNodes = new Noden; for(int i = 0; i < n; +i) secondNodesi = new Node(); for(int m = 0; m < n; +m) LinkedList<Integer> linkNodes

5、 = nodesm.getLinkNodes(); for(int q = 0; q < linkNodes.size(); +q) secondNodeslinkNodes.get(q).addLinkNodes(m); /* * 開始第二次搜索 */ secondDfs(secondNodes); public static void dfs(Node nodes) for(int i = 0; i < nodes.length; +i) if(nodesi.getColor() = Node.WHITE) dfsVisit(nodes,i); /* * 主要完成兩個工作：設(shè)置

6、顏色，設(shè)置時間戳 * 附加工作：記錄拓?fù)渑判驍?shù)組 * param nodes * param no */ public static void dfsVisit(Node nodes,int no) time+; nodesno.setColor(Node.GRAY); nodesno.setD(time); LinkedList<Integer> linkNodes = nodesno.getLinkNodes(); for(int i = 0; i < linkNodes.size(); +i) Node temp = nodeslinkNodes.get(i); if(

7、temp.getColor() = Node.WHITE) temp.setParent(nodesno); dfsVisit(nodes,linkNodes.get(i); nodesno.setColor(Node.BLACK); topology.add(no); time+; nodesno.setF(time); /* * 與第一次的dfs基本相同，唯一的不同是遍歷順序按照拓?fù)渑判蜻M(jìn)行 * param nodes 圖G的節(jié)點(diǎn)數(shù)組 */ public static void secondDfs(Node nodes) for(int i = topology.size() - 1; i

8、 >= 0; -i) if(nodestopology.get(i).getColor() = Node.WHITE) secondDfsVisit(nodes,topology.get(i); /* * 與第一次dfsVisit基本相同，具體有“兩增兩減”，不同點(diǎn)如下： * 1.增加輸出當(dāng)前結(jié)點(diǎn)編號 * 2.不再記錄時間戳（因?yàn)楹竺娌粫儆玫竭@些數(shù)據(jù)） * 3.不再記錄拓?fù)渑判颍ㄒ驗(yàn)楹竺娌粫儆玫竭@些數(shù)據(jù)） * 4.回到優(yōu)先搜索森林深度為1的節(jié)點(diǎn)（即沒有設(shè)置父節(jié)點(diǎn)的節(jié)點(diǎn)）時，輸出換行，代表一個強(qiáng)連通分量的結(jié)束 * param nodes 圖G的節(jié)點(diǎn)數(shù)組 * param no 當(dāng)前父結(jié)點(diǎn)

9、 */ public static void secondDfsVisit(Node nodes,int no) System.out.print(no + " "); nodesno.setColor(Node.GRAY); LinkedList<Integer> linkNodes = nodesno.getLinkNodes(); for(int i = 0; i < linkNodes.size(); +i) Node temp = nodeslinkNodes.get(i); if(temp.getColor() = Node.WHITE) te

10、mp.setParent(nodesno); secondDfsVisit(nodes,linkNodes.get(i); nodesno.setColor(Node.BLACK); if(nodesno.getParent() = null) System.out.println(); class Node public static final int WHITE = 0; public static final int GRAY = 1; public static final int BLACK = 2; private int color = WHITE; private int d

11、 = 0; private int f = 0; private Node parent = null; private LinkedList<Integer> linkNodes = null; public Node() linkNodes = new LinkedList<>(); public int getColor() return color; public void setColor(int color) this.color = color; public int getD() return d; public void setD(int d) thi

12、s.d = d; public int getF() return f; public void setF(int f) this.f = f; public Node getParent() return parent; public void setParent(Node parent) this.parent = parent; public LinkedList<Integer> getLinkNodes() return linkNodes; public void setLinkNodes(LinkedList<Integer> linkNodes) thi

13、s.linkNodes = linkNodes; public void addLinkNodes(int no) linkNodes.add(no); 基本原理： 整個算法圍繞著一個核心思想求解：對于圖G總是從f(U)大的強(qiáng)連通分量指向f(U)小的強(qiáng)連通分量，對于G的轉(zhuǎn)置Gt，則總是根據(jù)第一步算出來的f(U)，從f(U)小的強(qiáng)連通分量指向f(U)大的強(qiáng)連通分量（這里可以這樣理解，因?yàn)閺?qiáng)連通是雙向可達(dá)，所以轉(zhuǎn)置對于強(qiáng)連通內(nèi)部沒有影響，對強(qiáng)連通分量之間，則指向關(guān)系發(fā)生了反轉(zhuǎn)）。這里關(guān)于圖G的f(U)的大小問題，待會會做證明，我們先往下看。現(xiàn)在我們證明，對于圖G總是從f(U)大的強(qiáng)連通分量指向f(U)小的強(qiáng)連通分量，假設(shè)存在(u,v)，u屬