摘要：樹是一副無環(huán)連通圖?；ゲ幌噙B的樹組成的集合稱為森林。表示無向圖的數(shù)據(jù)類型圖的基本操作的兩個構(gòu)造，得到頂點數(shù)和邊數(shù)，增加一條邊。該方法不符合第一個條件，上百萬個頂點的圖是很常見的空間不滿足。

四種重要的圖模型：

無向圖（簡單連接）

有向圖（連接有方向性）

加權(quán)圖（連接帶有權(quán)值）

加權(quán)有向圖（連接既有方向性又帶有權(quán)值）

定義：由一組頂點和一組能夠?qū)蓚€頂點相連的邊組成。

特殊：自環(huán)（一條連接一個頂點和其自身的邊）；平行邊（連接同一對頂點的兩條邊）

數(shù)學家將含有平行邊的圖稱為多重圖；將沒有平行邊或自環(huán)的圖稱為簡單圖?，F(xiàn)實當中，兩點就可以指代一條邊。

兩個頂點通過一條邊相連，稱這兩頂點相鄰，并稱該連接依附于這兩個頂點。

某個頂點的度數(shù)即為依附于它的邊的總數(shù)。

子圖是由一幅圖的所有邊的一個子集（以及它們所依附的所有頂點）組成的圖。

路徑是由邊順序連接的一系列頂點。

簡單路徑是一條沒有重復頂點的路徑。

環(huán)是一條至少含有一條邊且起點和終點相同的路徑。

簡單環(huán)是一條（除了起點和終點必須相同之外）不含有重復頂點和邊的環(huán)。

路徑或者環(huán)的長度為其中所包含的邊數(shù)。

大多情況研究簡單環(huán)和簡單路徑，并會省略簡單二字。當允許重復的頂點時，指的都是一般的路徑和環(huán)。

當兩個頂點之間存在一條連接雙方的路徑時，稱一個頂點和另一個頂點是連通的。

U-V-W-X記為U到X的一條路徑；U-V-W-X-U記為U到V到W到X再回到U的一條環(huán)。

從任意一個頂點都存在一條路徑到達另一個任意頂點，稱這幅圖是連通圖。

一副非連通的圖由若干連通的部分組成，它們都是其極大連通子圖。

直觀上：如果頂點是念珠，邊是連接念珠的線，它們都是物理存在的對象，那么將任意頂點提起來，連通圖都將是一個整體，而非連通圖則會變成兩個或多個部分。

一般來說：要處理一張圖就要一個個地處理它的連通分量（子圖）。

無環(huán)圖：不包含環(huán)的圖。

樹是一副無環(huán)連通圖。互不相連的樹組成的集合稱為森林。連通圖的生成樹是它的一副子圖，它含有圖中的所有頂點且是一棵樹。圖的生成樹森林是它的所有連通子圖的生成樹的集合。

樹的定義非常通用，稍作改動就可以變成用來描述程序行為的（函數(shù)調(diào)用層次）模型和數(shù)據(jù)結(jié)構(gòu)（二叉查找樹、2-3樹等）。

當且僅當一幅含有V個節(jié)點的圖G滿足下列5個條件之一時，它就是一棵樹：

G有V-1條邊且不含有環(huán)；

G有V-1條邊且是連通的；

G是連通的，但刪除任意一條邊都會使之不再連通；

G是無環(huán)圖，但添加任意一條邊都會產(chǎn)生一條環(huán)；

G中的任意一對頂點之間僅存在一條簡單路徑。

圖的密度是指已經(jīng)連接的頂點對占所有可能被連接的的頂點對的比例。一般來說，如果一幅圖中不同的邊的數(shù)量只占頂點總數(shù)V的一小部分，那么就認為這幅圖是稀疏的，否則是稠密的。

二分圖是一種能夠?qū)⑺泄?jié)點分為兩部分的圖，其中圖的每條邊所連接的兩個頂點都分別屬于不同的部分。二分圖會出現(xiàn)在許多場景中。

圖的基本操作的API：

兩個構(gòu)造，得到頂點數(shù)V( )和邊數(shù)E( )，增加一條邊addEdge( int v, int w )。本節(jié)所有算法都基于adj( )方法所抽象的基本操作。第二個構(gòu)造函數(shù)接受的輸入由2E+2個整數(shù)組成：首先是V, 然后是E， 在然后是 E 對 0到V-1之間的整數(shù)，每個整數(shù)對都表示一條邊。

要面對的下一個圖處理問題就是用哪種數(shù)據(jù)結(jié)構(gòu)來表示并實現(xiàn)這份API，這包含兩個要求：

必須為可能在應(yīng)用中碰到的各種類型的圖預留出足夠的空間；

實例方法的實現(xiàn)一定要快—它們是開發(fā)處理圖的各種用例的基礎(chǔ)。

要求比較模糊，但是仍然能幫我們在三種圖的表示方法中進行選擇。

鄰接矩陣。用V*V的布爾矩陣，當V和W有邊時，定義V行W列元素為TRUE，否則為FALSE。該方法不符合第一個條件，上百萬個頂點的圖是很常見的.V^2空間不滿足。

邊的數(shù)組?？梢允褂靡粋€Edge類，含有兩個int實例變量。表示方法簡單但是不滿足第二個條件—要實現(xiàn)adj( )需要檢查所有邊。

鄰接表數(shù)組。可以使用一個以頂點為索引的列表數(shù)組，其中每個元素都是和該頂點相鄰的頂點列表。該結(jié)構(gòu)同時滿足兩個條件。本章一直用它。

除了性能目標，還發(fā)現(xiàn)：允許存在平行邊相當于排除了鄰接矩陣，因為鄰接矩陣無法表示它們。

非稠密圖的標準表示稱為鄰接表的數(shù)據(jù)結(jié)構(gòu)，它將每個頂點的所有相鄰頂點都保存在該頂點對于的元素所指向的一張鏈表中。使用這個數(shù)組就是為了快速訪問給定頂點的鄰接頂點列表。

使用Bag抽象數(shù)據(jù)類型(也可用Java中的)來實現(xiàn)這個鏈表，這樣就可以在常數(shù)時間內(nèi)添加新的邊或遍歷任意頂點的所有相鄰頂點。

這種Graph的實現(xiàn)的性能：

使用的空間和V+E成正比；

添加一條邊所需要的時間為常數(shù)；

遍歷頂點V的所有相鄰頂點所需要的時間和V的度數(shù)成正比。

對于這樣的操作，這樣的特性已經(jīng)是最優(yōu)，可以滿足圖處理應(yīng)用的需要，并且支持平行邊和自環(huán)。邊的插入順序決定了Graph得鄰接表中頂點的出現(xiàn)順序。使用構(gòu)造函數(shù)從標準輸入中讀入一副圖時，就意味著輸入的格式和邊的順序決定了Graph的鄰接表數(shù)組中頂點的出現(xiàn)順序。

/**
 * 無向圖
 */
public class Graph {
    private int vertexCount;            // 頂點數(shù)
    private int edgeCount;                // 邊數(shù)
    private LinkedList[] adj;    // 鄰接表數(shù)組
    public Graph(int v){
        this.adj = new LinkedList[v];
        for(int i = 0; i();// 初始化鄰接表數(shù)組
        this.vertexCount = v;
    }
    public Graph(In in) {
        this(in.readInt());
        int e = in.readInt();//得到邊數(shù)
        // 讀取每條邊，進行圖的初始化操作
        for(int i = 0; i adj(int v){return adj[v];}
    /** 把圖轉(zhuǎn)化成標準字符串形式*/
    public String toString(){
        String NEWLINE = System.getProperty("line.separator");
        StringBuilder sb = new StringBuilder();
        sb.append("vertex count: ").append(getVertexCount())
                .append(" edge count: ").append(getEdgeCount())
                .append(Config.NEWLINE);
        for (int v = 0; v < getVertexCount();v++){
            LinkedList list = adj(v);
            sb.append(v).append(":	").append("[");
            for (int i=0; i < list.size();i++){
                sb.append(list.get(i)).append(",");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append("]").append(NEWLINE);
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        String dir = Graph.class.getPackage().getName().replace(".", "/");
        String path = Graph.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        System.out.println(g.toString());
    }
}

/**
 * 圖的基本常用操作工具類
 */
public class GraphUtils {
    /** 計算頂點v的度數(shù)*/
    public static int degree(Graph graph, int v){return graph.adj(v).size();}
    /** 計算圖中最大的度*/
    public static int maxDegree(Graph graph){
        int max = 0;
        for(int i = 0;i max ? currentDegree : max;
        }
        return max;
    }
    /** 計算圖的平均度數(shù)*/
    public static int avgDegree(Graph g){ return 2 * g.getEdgeCount() / g.getVertexCount(); }
    /** 計算自環(huán)的個數(shù)*/
    public static int numberOfSelfLoops(Graph g){
        int count = 0;
        for(int v = 0; v < g.getVertexCount(); v++)
            for(int w: g.adj(v))
                if(v == w)    count++;
        return count / 2; // 每條邊計算了兩次
    }
    public static void main(String[] args) {
        String dir = GraphUtils.class.getPackage().getName().replace(".", "/");
        String path = GraphUtils.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        for (int i = 0; i < g.getVertexCount(); i++) {
            System.out.println(i+" degree : "+GraphUtils.degree(g, i));    
        }
        System.out.println("the max degree is : " + GraphUtils.maxDegree(g));
        System.out.println(g.toString());
        System.out.println("avg degree: "+GraphUtils.avgDegree(g));
        System.out.println("count of self loop: "+GraphUtils.numberOfSelfLoops(g));
    }
}

0 degree : 4
1 degree : 1
2 degree : 1
3 degree : 2
4 degree : 3
5 degree : 3
6 degree : 2
7 degree : 1
8 degree : 1
9 degree : 3
10 degree : 1
11 degree : 2
12 degree : 2
the max degree is : 4
vertex count: 13 edge count: 13
0:    [5,1,2,6]
1:    [0]
2:    [0]
3:    [4,5]
4:    [3,6,5]
5:    [0,4,3]
6:    [4,0]
7:    [8]
8:    [7]
9:    [12,10,11]
10:    [9]
11:    [12,9]
12:    [9,11]

avg degree: 2
count of self loop: 0

將圖的表示和實現(xiàn)分離開。為每個任務(wù)創(chuàng)建一個相應(yīng)的類，用例可以創(chuàng)建相應(yīng)的對象來完成任務(wù)。

探索迷宮方法：tremaux搜索：

選擇一條沒有標記過的通道，在走過的路上鋪一條繩子；

標記所有你第一次路過的路口和通道；

當來到一個標記過的路口時（用繩子）回退到上一個路口；

當回退到得路口已經(jīng)沒有可走的通道時繼續(xù)回退。

繩子可保證總能找到一條出路，標記則能保證不會兩次經(jīng)過同一條通道或同一個路口。

看Java代碼實現(xiàn)：

/**
 * 圖的深度優(yōu)先搜索算法
 */
public class DepthFirstSearch {
    private int count;
    private boolean[] marked; // 數(shù)組存儲每個頂點是否被遍歷過
    /**
     * 從頂點s開始對g進行深搜
     * @param g
     * @param s
     */
    public DepthFirstSearch(Graph g, int s) {
        marked = new boolean[g.getVertexCount()];
        dfs(g, s);
    }
    /** 深搜*/
    private void dfs(Graph g, int s) {
        marked[s] = true;                    // 1.標記頂點s
        count++;                            // 2.count數(shù)加一
        LinkedList list = g.adj(s);// 3.獲取s的鄰接表
        for(int w: list)                    // 4.對鄰接表進行遍歷
            if(!isMarked(w))    dfs(g,w);    // 5.如果遍歷到的頂點沒有被標記過，對該頂點繼續(xù)遞歸深搜
    }
    /** 頂點w是否和起點s相連通*/
    public boolean isMarked(int w){return marked[w];}
    
    /** 與起點s連通的頂點數(shù)量*/
    public int count(){return count;}
    
    public static void main(String[] args) {
        String dir = DepthFirstSearch.class.getPackage().getName().replace(".", "/");
        String path = DepthFirstSearch.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        int start = 0;
        DepthFirstSearch search = new DepthFirstSearch(g, start);
        System.out.print("start vertex: "+ start+". ");
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i< g.getVertexCount(); i++)
            if(search.isMarked(i)) sb.append(" "+ i);
        System.out.println("Connected " + sb.toString());
        // 如果和s連通的頂點數(shù)量和圖的頂點數(shù)量相同，說明是連通圖
        if(search.count() == g.getVertexCount())    System.out.println("g is a connected graph.");
        else System.out.println("g is not a connected graph.");
    }
}

start vertex: 0. Connected  0 1 2 3 4 5 6
g is not a connected graph.

“兩個給定頂點是否連通？”等價于“兩個給定的頂點之間是否存在一條路徑”，也叫路徑檢測問題。

union-find算法的數(shù)據(jù)結(jié)構(gòu)并不能解決找出這樣一條路徑問題，DFS是已經(jīng)學習過的方法中第一個能夠解決該問題的算法

能解決的另一問題：單點路徑----給定一幅圖和一個起點s，“從S到給定的頂點V是否存在一條路徑，如果有，找出”

構(gòu)造函數(shù)接受一個起點S作為參數(shù)，計算S到與S連通的每個頂點之間的路徑。在為S創(chuàng)建了Paths對象后，用例可以調(diào)用pathTo()實例方法來遍歷從S到任意和S連通的頂點的路徑上的所有頂點。以后會實現(xiàn)只查找具有某些屬性的路徑。

Java實現(xiàn)

/**
 * 深搜尋找路徑問題
 */
public class DepthFirstPaths {
    private boolean[] marked;        
    private int[] edgeTo;        // 路徑
    private int start;            // 起點
    public DepthFirstPaths(Graph g, int s){
        marked = new boolean[g.getVertexCount()];
        edgeTo = new int[g.getVertexCount()];
        this.start = s;
        dfs(g, s);
    }
    private void dfs(Graph g, int s) {
        marked[s] = true;
        for(int w: g.adj(s)){
            if(!marked[w]){
                // 如果w沒有被標記過，把路徑數(shù)組中的w處置為s，意思：從s到達了w。此處記錄了每一次深搜的路徑節(jié)點
                edgeTo[w] = s; 
                dfs(g, w);
            }
        }
    }
    /** 從起點s到頂點v是否存在通路*/
    public boolean hasPathTo(int v){return marked[v];}
    public Stack pathTo(int v){
        if(!hasPathTo(v))    return null;
        Stack stack = new Stack<>();
        for(int x = v; x!=start; x=edgeTo[x]) // 從終點開始，倒著找起點，依次push入棧
            stack.push(x);
        stack.push(start);// for循環(huán)到起點處終止，所以在循環(huán)結(jié)束后要把起點入棧，至此 一條完整的路徑依次入棧
        return stack;
    }
    public static void main(String[] args) {
        String dir = DepthFirstPaths.class.getPackage().getName().replace(".", "/");
        String path = DepthFirstPaths.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        int start = 0;
        DepthFirstPaths pathSearch = new DepthFirstPaths(g, start);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i p = pathSearch.pathTo(i);
            while(!p.isEmpty()) sb.append(p.pop()).append("->");
            sb.deleteCharAt(sb.length()-1);
            sb.deleteCharAt(sb.length()-1);
            System.out.println(sb.toString());
        }
    }
}

0 to 1: 0->1
0 to 2: 0->2
0 to 3: 0->5->4->3
0 to 4: 0->5->4
0 to 5: 0->5
0 to 6: 0->5->4->6
0 to 7 : not connected.
0 to 8 : not connected.
0 to 9 : not connected.
0 to 10 : not connected.
0 to 11 : not connected.
0 to 12 : not connected.

深搜得到的路徑不僅取決于圖的結(jié)構(gòu)，還取決于圖的表示和遞歸調(diào)用的性質(zhì)。我們自然對最短路徑感興趣：

單點最短路徑。給定一幅圖和一個起點S，從S到給定頂點V是否存在一條路徑？如果有，請找出其中最短的那條（所含邊數(shù)最少）。

DFS遍歷圖的順序和找出最短路徑的目標無關(guān)。

BFS為了這個目標而出現(xiàn)。要找到從S到V得最短路徑，從S開始，在所有由一條邊就可以到達的頂點中查找V， 如果找不到就繼續(xù)在與S距離兩條邊的所有頂點中查找，如此一直執(zhí)行。

DFS好像是一個人在走迷宮，BFS則像一組人在一起朝各個方向走這個迷宮，每個人都有自己的繩子，當出現(xiàn)新的叉路時，可以假設(shè)一個探索者可以分裂為更多的人來搜索。當來個那個探索者相遇的時候，合二為一，并繼續(xù)使用先到達者的繩子。

在程序中，搜索一幅圖時遇到有多條邊需要遍歷的情況，我們會選擇其中一條并將其他通道留到以后再繼續(xù)搜索。在DFS中，用了一個可以下壓的棧，以支持遞歸搜索。使用LIFO的規(guī)則來描述壓棧和走迷宮時先探索相鄰的通道類似。從有待搜索的通道中選擇最晚遇到過的那條。

在BFS中希望按照與起點的距離的順序來遍歷所有的頂點：使用FIFO先進先出隊列來代替棧LIFO后進先出 即可。將從有待搜索的通道中選擇最早遇到的那條。

實現(xiàn)：

算法4.2實現(xiàn)了BFS。使用隊列保存所有已經(jīng)被標記過但其鄰接表還未被檢查過的頂點。先將起點加入隊列，然后重復下面步驟直到隊列為空：

取隊列中的下一個頂點V并標記它；

將與V相鄰的所有未被標記過的頂點加入隊列。

算法4.2中的方法不是遞歸的，不像遞歸中隱式使用的棧，而是顯式地使用了一個隊列。

從隊列中刪除0，將相鄰頂點2 1 5加入隊列，標記它們并分別將它們在edgeTo[ ]中的值置為0；隊列： 0 2 1 5

從隊列中刪除2，并檢查相鄰頂點0 1 3 4， 0和1已經(jīng)被標記，將3和4這兩個沒被標記的加入隊列，標記它們，并分別將它們在edgeTo[ ] 中的值設(shè)為2；隊列： 0 2 1 5 3 4

刪除1，檢查相鄰點0 2，發(fā)現(xiàn)都已經(jīng)被標記；隊列： 0 2 1 5 3 4

刪除5， 檢查相鄰點 0 3， 發(fā)現(xiàn)都已經(jīng)被標記；隊列： 0 2 1 5 3 4

刪除3， 檢查相鄰點 2 4 5， 發(fā)現(xiàn)都已經(jīng)被標記；隊列： 0 2 1 5 3 4

刪除4， 檢查相鄰點 2 3， 發(fā)現(xiàn)都已經(jīng)被標記；隊列： 0 2 1 5 3 4

/**
 * 廣搜找到最短路徑
 *         對于從s可達的任意頂點v，廣搜都能找到一條從s到v的最短路徑
 *         （沒有其他從s到v的路徑所含邊比這條路徑更少）
 * 廣搜所需時間在最壞情況下和（v + e）成正比。
 */
public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int start;
    public BreadthFirstPaths(Graph g, int s){
        this.start = s;
        marked = new boolean[g.getVertexCount()];
        edgeTo = new int[g.getVertexCount()];
        bfs(g, s);
    }
    private void bfs(Graph g, int s) {
        Queue queue = new Queue<>();    
        marked[s] = true;     // 標記起點
        queue.enqueue(s);    // 起點入隊
        while(!queue.isEmpty()){
            int head = queue.dequeue();    // 從隊列中取出隊首
            LinkedList list = g.adj(head);    // 得到隊首的鄰接表
            for(int w: list){     //遍歷鄰接表
                if(!marked[w]){    // 若當前節(jié)點沒有被標記過
                    edgeTo[w] = head;    // 1.存入路徑
                    marked[w] = true;    // 2.進行標記
                    queue.enqueue(w);    // 3.節(jié)點入隊
                }
            }
        }
    }
    /** 從起點s到頂點v是否存在通路*/
    public boolean hasPathTo(int v){return marked[v];}
    /** 返回從起點s到頂點v的一條最短路徑*/
    public Stack pathTo(int v){
        if(!hasPathTo(v))    return null; // 若不存在到v的路徑，返回Null
        Stack path = new Stack<>();
        for(int x = v; x!=start; x=edgeTo[x])
            path.push(x);
        path.push(start);
        return path;
    }
    public static void main(String[] args) {
        String dir = BreadthFirstPaths.class.getPackage().getName().replace(".", "/");
        String path = BreadthFirstPaths.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        int start = 5;
        BreadthFirstPaths bfPath = new BreadthFirstPaths(g, start);
        for(int i = 0; i p = bfPath.pathTo(i);
            while(!p.isEmpty()){
                sb.append(p.pop() + "->");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

5 to 0 : 5->0
5 to 1 : 5->0->1
5 to 2 : 5->0->2
5 to 3 : 5->3
5 to 4 : 5->4
5 to 6 : 5->0->6
5 to 7 : not connected.
5 to 8 : not connected.
5 to 9 : not connected.
5 to 10 : not connected.
5 to 11 : not connected.
5 to 12 : not connected.

對于這個例子，edgeTo[]數(shù)組在第二步之后就已經(jīng)完成了。和深搜一樣，一點所有頂點都已經(jīng)被標記，余下的計算工作就只是在檢查連接到各個已被標記的頂點的邊而已。

命題：對于從S可達到的任意頂點V， 廣搜都能找到一條從S到V的最短路徑(沒有其他從S到V得路徑所含的邊比這條路徑更少)

續(xù)： 廣搜所需的時間在最壞情況下和V+E成正比。

DFS和BFS都會先將起點存入數(shù)據(jù)結(jié)構(gòu)中，然后重復以下步驟知道數(shù)據(jù)結(jié)構(gòu)被清空：

取其中的下一個頂點并標記它；

將V的所有相鄰而又未被標記的頂點加入數(shù)據(jù)結(jié)構(gòu)。

不同之處在于從數(shù)據(jù)結(jié)構(gòu)中獲取下一個頂點的規(guī)則：廣搜是最早加入的頂點；深搜是最晚加入的頂點。這種差異得到了處理圖的兩種完全不同的視角，無論哪種，所有與起點連通的頂點和邊都會被檢查到。

深搜下一個直接應(yīng)用就是找出一幅圖的所有連通分量。API：

CC的實現(xiàn)使用了marked[ ]數(shù)組來尋找一個頂點作為每個連通分量中深度優(yōu)先搜索的起點。遞歸的深搜第一次調(diào)用的參數(shù)是頂點0，會標記所有與0連通的頂點。然后構(gòu)造函數(shù)中的for循環(huán)會查找每個沒有被標記的頂點并遞歸調(diào)用dfs來標記和它相鄰的所有頂點。另外，它還使用了一個以頂點作為索引的數(shù)組id[ ],將同一個連通分量中的頂點和連通分量的標識符關(guān)聯(lián)起來。這個數(shù)組使得connected( )方法的實現(xiàn)變得十分簡單。

/**
 * 強連通分量
 */
public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;
    public CC(Graph g){
        marked = new boolean[g.getVertexCount()];
        id = new int[g.getVertexCount()];
        for(int s = 0; s < g.getVertexCount(); s++){
            if(!marked[s]){
                dfs(g,s);
                count++;
            }
        }
    }
    private void dfs(Graph g, int v) {
        marked[v] = true;
        id[v] = count;
        for(int w: g.adj(v))
            if(!marked[w])
                dfs(g,w);
    }
    /** v和w連通嗎*/
    public boolean connected(int v, int w)    { return id[v] == id[w]; }
    /** v所在的連通分量的標識符*/
    public int id(int v)    { return id[v]; }
    /** 連通分量數(shù)*/
    public int count()        {return count;}
    public static void main(String[] args) {
        String dir = CC.class.getPackage().getName().replace(".", "/");
        String path = CC.class.getClassLoader().getResource(dir+"/tinyG.txt").getPath();
        In in = new In(new File(path));
        Graph g = new Graph(in);
        CC cc = new CC(g);
        int m = cc.count();
        System.out.println("number of components: "+ m);
        LinkedList[] components = new LinkedList[m];
        for(int i =0;i();
        for(int v = 0; v< g.getVertexCount(); v++)
            components[cc.id(v)].add(v);
        for(int i=0;i
number of components: 3
0 1 2 3 4 5 6 
7 8 
9 10 11 12 
其實現(xiàn)基于一個由頂點索引的數(shù)組id[ ].若V屬于第i個連通分量，則id[v]的值為i。構(gòu)造函數(shù)會找出一個未被標記的頂點并調(diào)用遞歸函數(shù)dfs( )來標記并區(qū)分出所有和它連通的頂點，如此重復直到所有的頂點都被標記并區(qū)分。
命題C：深搜的預處理使用的時間和空間與V+E成正比且可以在常數(shù)時間內(nèi)處理關(guān)于圖的連通性查詢。

和union-find算法對比：理論上深搜比union-find快，因為能保證所需時間是常數(shù)，而union-find不行；但在實際中，該差異微不足道。union-find更快，因為它不需要完整的構(gòu)造并表示一幅圖。更重要的是：union-find算法是一種動態(tài)算法（在任何時候都能用接近常數(shù)的時間檢查兩個頂點是否連通，甚至是在添加一條邊的時候），但深搜就必須對圖進行預處理。

因此，在完成只需要判斷連通性或是需要完成有大量連通性查詢和插入操作混合等類似的任務(wù)時，更傾向使用union-find,而深搜更適合實現(xiàn)圖的抽象數(shù)據(jù)類型，因為能夠更有效的利用已有數(shù)據(jù)結(jié)構(gòu)。



DFS已經(jīng)解決了幾個基礎(chǔ)問題。該方法很簡單，遞歸實現(xiàn)使得我們能夠進行復雜的運算并為一些圖的處理問題給出簡潔的解決方法。
下面對兩個問題進行解答：

檢測環(huán)：給定的圖是無環(huán)圖嗎？

雙色問題：能夠用兩種顏色將圖的所有頂點著色，使得任意一條邊上的兩個端點的顏色都不同嗎？這個問題等價于：這是一幅二分圖嗎？


檢測環(huán)解題：
/**
 * 給定的圖是無環(huán)圖嗎
 * 檢測自環(huán):假設(shè)沒有自環(huán)，沒有平行邊
 */
public class Cycle {
    private boolean[] marked;
    private boolean hasCycle;
    public Cycle(Graph g){
        marked = new boolean[g.getVertexCount()];
        for(int i = 0;i
true
false

雙色問題解題
/**
 * 雙色問題：能夠用兩種顏色將圖的所有頂點著色，使得任意一條邊上的兩個端點的顏色都不同嗎？
 * 等價于：判斷是否是二分圖的問題
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isColorable;
    public TwoColor(Graph g){
        isColorable = true;
        marked = new boolean[g.getVertexCount()];
        color = new boolean[g.getVertexCount()];
        for(int i = 0; i
true
false

符號圖
典型應(yīng)用中，圖都是通過文件或者網(wǎng)頁定義的，使用的是字符串而非整數(shù)來表示和指代頂點。為了適應(yīng)這樣的應(yīng)用，定義擁有以下性質(zhì)的輸入格式：

頂點名為字符串

用指定的分隔符來隔開頂點名（允許頂點名中含有空格）

每一行都表示一組邊的集合，每條邊都連接著這一行的第一個名稱表示的頂點和其他名稱所表示的頂點

頂點總數(shù)V和邊的總數(shù)E都是隱式定義的。


例子：

API

定義了一個構(gòu)造來讀取并構(gòu)造圖，用name( )方法和index( )方法將輸入流中的頂點名和圖算法使用的頂點索引對應(yīng)起來。
測試用例
例子：飛機場routes.txt--輸入機場代碼查找從該機場起飛到達的城市，但這些信息并不是直接從文件中能得到的。
例子：電影movies.txt--輸入一部電影名字得到演員列表。這不過是在照搬文件中對應(yīng)的行數(shù)據(jù)，
?                                    但輸入演員名字 查看其出演的電影列表，相當于反向索引。
?                                    盡管數(shù)據(jù)庫的構(gòu)造是為了將電影名連接到演員，二分圖模型同時也意味著將演員連接到電影名。
?            二分圖的性質(zhì)自動完成了反向索引。這將成為處理更復雜的和圖有關(guān)的問題的基礎(chǔ)。
符號圖的實現(xiàn)
SymbolGraph用到了3種數(shù)據(jù)結(jié)構(gòu)：

一個符號表st,鍵的類型為String（頂點名），值得類型為int（索引）；

一個數(shù)組keys[ ]，用作反向索引，保存每個頂點索引對應(yīng)的頂點名；

一個Graph對象G，使用索引來引用圖中的頂點。


SymbolGraph會遍歷兩遍數(shù)據(jù)結(jié)構(gòu)來構(gòu)造以上數(shù)據(jù)結(jié)構(gòu)，主要是因為構(gòu)造Graph對象需要頂點總數(shù)V。在典型的實際應(yīng)用中，在定義圖的文件中指明V和E可能會不方便，從而有了SymbolGraph,這樣就可以方便地在routes.txt或者movies.txt中添加或者刪除條目而不用但系需要維護邊或者頂點的總數(shù)。

Java實現(xiàn)
/**
 * 符號圖
 */
public class SymbolGraph {
    private HashMap map;     // key:頂點名  value:索引
    private String[] keys;                    // 反向索引，保存每個頂點索引對應(yīng)的頂點名
    private Graph g;                        // 使用索引來引用圖中的頂點
    public SymbolGraph(String path, String sp){
        map = new HashMap<>();
        BufferedReader reader;
        String line;
        try {
            reader = new BufferedReader(new FileReader(new File(path)));
            while((line = reader.readLine()) != null){//第一遍，構(gòu)造索引
                String [] vertexs = line.split(sp);
                for(String s : vertexs)
                    if(!map.containsKey(s))    map.put(s, map.size());
            }
            reader.close();
            keys = new String[map.size()]; 
            for(String name: map.keySet()){    // 遍歷map的key,構(gòu)造頂點名的反向索引
                keys[map.get(name)] = name; 
            }
            g = new Graph(map.size());
            line = "";
            reader = new BufferedReader(new FileReader(new File(path)));
            while((line = reader.readLine()) != null){ // 第二遍，構(gòu)造圖，將每一行的頂點和該行其他點相連
                String[] strs = line.split(sp);
                int start = map.get(strs[0]);//獲取起點
                for(int i = 1; i< strs.length; i++)
                    g.addEdge(start, map.get(strs[i]));
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    /** key是一個頂點嗎*/
    public boolean  contains(String key){return map.containsKey(key);}
    /** key的索引*/
    public int index(String key){return map.get(key);}
    /** 索引v的頂點名*/
    public String name(int v){return keys[v];}
    /** 隱藏的Graph對象*/
    public Graph graph(){return g;}
    public static void main(String[] args) {
        String dir = Cycle.class.getPackage().getName().replace(".", "/");
        String path = Cycle.class.getClassLoader().getResource(dir+"/routes.txt").getPath();
        SymbolGraph sg = new SymbolGraph(path, " ");
        Graph g = sg.graph();
        HashMap map = sg.map;
        for(Entry s: map.entrySet()){
            System.out.println(s.getKey() + "-" +s.getValue());
        }
        System.out.println(g.toString());
        String start = "JFK";
        if(!sg.contains(start)){
            System.out.println("起點"+start + " 不在數(shù)據(jù)庫.");
            return;
        }
        int s = sg.index(start);
        BreadthFirstPaths bfs = new BreadthFirstPaths(g, s);
        String end = "LAS";
        if(!sg.contains(end)){
            System.out.println("終點"+end + " 不在數(shù)據(jù)庫.");
        }else{
            int t = sg.index(end);
            if(!bfs.hasPathTo(t)){
                System.out.println(start +" 和 " + end + " 沒有路徑相同.");
                return;
            }
            Stack stack = bfs.pathTo(t);
            StringBuilder sb = new StringBuilder();
            while(!stack.isEmpty()){
                sb.append(sg.name(stack.pop())).append(" ");
            }
            System.out.println("起點"+start+"到終點"+end+"的路徑為:");
            System.out.println(sb.toString());
        }
    }
}
LAS-9
LAX-8
DFW-5
ORD-2
JFK-0
HOU-4
ATL-7
DEN-3
PHX-6
MCO-1
vertex count: 10 edge count: 18
0:    [1,7,2]
1:    [0,7,4]
2:    [3,4,5,6,0,7]
3:    [2,6,9]
4:    [2,7,5,1]
5:    [6,2,4]
6:    [5,2,3,8,9]
7:    [0,4,2,1]
8:    [6,9]
9:    [3,8,6]

起點JFK到終點LAS的路徑為:
JFK ORD DEN LAS 
同樣可以把電影-演員作為例子輸入：
這個Graph實現(xiàn)允許用例用字符串代替數(shù)字索引來表示圖中的頂點。
它維護了

實例變量st（符號表用來映射頂點名和索引）

keys（數(shù)組用來映射索引和頂點名）

g（使用索引表示頂點的圖）


為了構(gòu)造這些數(shù)據(jù)結(jié)構(gòu)，代碼會將圖的定義處理兩遍（定義的每一行都包含一個頂點以及它的相鄰頂點列表，用分隔符sp隔開）
間隔的度數(shù)
圖處理的一個經(jīng)典問題就是，找到一個社交網(wǎng)絡(luò)之中兩個人間隔的度數(shù)。
演員K演過很多電影，為圖中每個演員附一個K數(shù)：

K本人為0，

所有和K演過同一部電影的人的值為1，

所有（除K外）和K數(shù)為1的演員出演過同一部電影的人的值為2，

以此類推。


可以看到K數(shù)必須為最短電影鏈的長度，因此不用計算機，很難知道。
用例DegreesOfSeparation所示，BreadthFirstPaths才是我們所需要的程序，通過最短路徑來找出movies.txt中任意演員的K數(shù)。
總結(jié)
幾個基本概念：

圖的術(shù)語；

一種圖的表示方法，能夠處理大型而稀疏的圖；

和圖處理相關(guān)的類的設(shè)計模式，其實現(xiàn)算法通過在相關(guān)的類的構(gòu)造函數(shù)中對圖進行預處理，構(gòu)造所需的數(shù)據(jù)結(jié)構(gòu)來高效支持用例對圖的查詢；

DFS&BFS

支持使用符號作為圖的頂點名的類。



上表總結(jié)了本節(jié)所有圖算法的實現(xiàn)。適合作為圖處理的入門學習。隨后學習復雜類型圖以及更加困難的問題時，會用到這些代碼的變種。
考慮了邊的方向以及權(quán)重之后，同樣地問題會變得困難得多，但同樣地算法仍然湊效并將成為解決更復雜問題的起點。