[[381783]]

 1. 基本概念

圖的基本概念中我們需要掌握的有這么幾個概念：無向圖、有向圖、帶權(quán)圖;頂點(vertex);邊(edge);度(degree)、出度、入度。下面我們就從無向圖開始講解這幾個概念。

如圖所示是一個無向圖，圖中的元素(A、B、C、D、E、F)被稱為頂點(vertex)，頂點可以與任意頂點建立連接關(guān)系，這種關(guān)系叫做邊(edge)，無向圖中邊是沒有方向的。頂點相連接的邊的條數(shù)就被稱為度(degree)，圖中頂點 A 的度就是 3 。

還有一種圖，圖中的邊是有方向的，如圖所示，則將這種圖稱為有向圖。度這種概念在有向圖中又被擴展為入度和出度。頂點的入度是指有多少條邊指向這個頂點;頂點的出度指有多少條邊以這個頂點為起點。

上述的邊都沒有權(quán)重，假如我們要拿一個圖來存儲地圖數(shù)據(jù)的話，圖中的邊還需要表示距離，那么這個圖就變成了帶權(quán)圖(weighted graph)。在帶權(quán)圖中，每條邊都有一個權(quán)重，這個權(quán)重可以表示距離。

★綜上來看的，圖的類型主要是根據(jù)邊的類型來決定的。”

2. 圖的存儲

圖的基本概念不多，那么在計算機中我們該如何存儲圖這種數(shù)據(jù)結(jié)構(gòu)呢?主要有兩種方式來存儲圖，一種是鄰接矩陣的方法，另一種是鄰接表的方式。

2.1. 鄰接矩陣

鄰接矩陣是圖最直觀的一種存儲方式，底層依賴于二維數(shù)組。

• 對于無向圖來說，如果頂點 i 和頂點 j 之間有邊那么則將 A[i][j] 和 A[j][i] 標記為 1
• 對于有向圖來說，如果頂點 i 有一條邊指向頂點 j，但是頂點 j 沒有一條邊指向頂點 i，那么則將 A[i][j] 標記為 1，但是 A[j][i] 不用標記為 1。
• 對于帶權(quán)圖來說，只是從存儲 1 變成存儲具體的權(quán)重。

• 鄰接矩陣的缺點是在表示一個圖時通常很浪費存儲空間。

對于無向圖來說，它是一個對稱矩陣，即 A[i][j] 等于 1 的話，那么 A[j][i] 也等于 1。那么實際上只要存儲一半就可以了。

另外，假如存儲的是稀疏圖，也就是頂點很多，但是每個頂點的邊不多的一種圖。那么使用鄰接矩陣存儲將更浪費存儲空間，因為很多位置的值都是 0，這些 0 其實都是沒有用的。

• 鄰接矩陣的優(yōu)點就是存儲方式簡單、直觀，而且獲取兩個頂點的關(guān)系時非常高效。另外，使用鄰接矩陣時，在計算上也很方便。因為很多圖的運算實際上可以轉(zhuǎn)換為矩陣的運算，比如求最短路徑問題時會提到一個 Floyd-Warshall 算法，這個算法會利用到矩陣循環(huán)相乘若干次的結(jié)果。

2.2. 鄰接表

圖的另一種存儲方法，是使用鄰接表(Adjacency List)。如圖所示，有向圖中的每個頂點對應(yīng)一個鏈表，該鏈表中存儲的是該頂點指向的頂點。對于無向圖來說是類似的，每個節(jié)點對應(yīng)的鏈表中存儲的是該節(jié)點所相連的頂點。

• 鄰接表相比鄰接矩陣的一個優(yōu)點就是節(jié)省空間，但是使用起來比較耗時間(時間換空間的設(shè)計思想)。在使用鄰接矩陣判斷無向圖中 i 和 j 之間是否存在一條邊，那么只需要判斷 A[i][j] 是否為 1，而在鄰接表中判斷無向圖中 i 和 j 之間是否存在一條邊，那么需要判斷 i 這個頂點對應(yīng)的鏈表中是否存在 j。而且鏈表的方式對于緩存來說不太友好。所以，綜上來說在鄰接表中查詢兩個頂點的關(guān)系沒有鄰接矩陣那么高效了。
• 但是，為了讓查詢變得更加高效。我們可以參考散列表中提到的那樣，將鏈表換成平衡二叉查找樹(比如紅黑樹)，或者其他動態(tài)數(shù)據(jù)結(jié)構(gòu)，比如跳表、散列表，有序動態(tài)數(shù)組(結(jié)合二分查找)等。

逆鄰接表

鄰接表中存儲的是這個頂點指向的頂點，那么逆鄰接表中存儲的是指向這個頂點的頂點。比如要想查看 4 這個頂點指向了哪些節(jié)點就可以使用鄰接表。但是想要查看有哪些節(jié)點指向了 4 這個頂點，那么就需要逆鄰接表了。

2.3. 總結(jié)

綜上來說，鄰接矩陣的缺點是比較浪費空間，但是優(yōu)點是查詢效率高，還方便矩陣運算。鄰接表的優(yōu)點是節(jié)省存儲空間，但是不方便查找(查找效率肯定沒鄰接矩陣高)。對于此，我們可以將鏈表替換成查詢效率較高的動態(tài)數(shù)據(jù)結(jié)構(gòu)，比如平衡二叉樹(紅黑樹)、跳表、散列表等。

3. 圖的搜索

圖上的搜索算法，最直接的理解就是，在圖中找出從一個頂點出發(fā)，到另一個頂點的路徑。具體方法有很多，比如有最簡單、最“暴力”的深度優(yōu)先、廣度優(yōu)先搜索，還有 A*、IDA* 等啟發(fā)式搜索算法。深度優(yōu)先、廣度優(yōu)先搜索即可以用在有向圖，也可以用在無向圖上。下面的實現(xiàn)以無向圖和鄰接表的存儲方式為例。

3.1. 廣度優(yōu)先搜索(Breath-First-Search)

廣度優(yōu)先搜索，簡稱 BFS。這種搜索方法是一層層的向外搜索，先從起點開始，然后再搜索離起點最近的頂點;之后再從離起點最近的頂點出發(fā)搜索離這些頂點最近的頂點。整個過程示意圖如圖所示，跟二叉樹的層次遍歷是一樣的。

相應(yīng)的代碼實現(xiàn)，如下代碼所示。from 表示起點，to 表示終點。和層次遍歷一樣，廣度優(yōu)先搜索使用了隊列這種數(shù)據(jù)結(jié)構(gòu)。隊列主要用來存儲那些已經(jīng)被訪問，但是相鄰的頂點還沒有被訪問的頂點。為什么使用隊列這種數(shù)據(jù)結(jié)構(gòu)呢?從應(yīng)用場景出發(fā)，因為廣度優(yōu)先搜索方法是逐層訪問的。也就是先訪問 k 層的頂點，訪問之后再去訪問 k+1 層的頂點。但是，在訪問第 k 層頂點的時候需要將 k+1 層的頂點也保存下來，而且 k+1 層頂點是在第 k 層頂點之后被訪問并從隊列中退出，也就相當于 “后來后出”。

但是，相比層次遍歷又多一些內(nèi)容，主要多出的是 visited 和 paths 這兩個數(shù)組，visited 數(shù)組主要是用來存儲頂點是否已經(jīng)被訪問過了，因為圖相比樹更為復(fù)雜，有些頂點會有多個相鄰頂點。為了避免頂點被重復(fù)訪問，所以借用了一個數(shù)組。

paths 數(shù)組主要用來記錄從 from 到 to 的廣度搜索路徑，但是每個數(shù)組元素(數(shù)組下標即頂點編號)只存儲該頂點前面的那個頂點，比如 paths[3] 存儲 2，則表示是先訪問到 2 ，然后從 2 再訪問到 3。這樣的存儲方式是逆向的，為了正向地輸出搜索路徑，可以使用遞歸的方式，遞歸的時候?qū)⑤敵龇胖玫竭f歸之后。因為只有等前面的頂點遞歸完成之后，再輸出本頂點，才是正向的路徑。

public void bfsSearch(int from, int to) { 
    if (this.v == 0 || from == to) { 
        return; 
    } 
 
    boolean[] visited = new boolean[this.v]; 
    int[] paths = new int[this.v]; // 記錄路徑，記錄該節(jié)點前面的節(jié)點是哪個    
    for (int i = 0; i < this.v; i++) { 
        visited[i] = false; 
        paths[i] = -1; 
    } 
 
    Queue<Integer> queue = new LinkedList<>(); 
    queue.offer(from); 
    visited[from] = true; 
 
    while (!queue.isEmpty()) { 
        int w = queue.poll(); 
 
        for (Integer i : this.adj[w]) { 
            if (!visited[i]) { 
                queue.offer(i); 
                visited[i] = true; 
                paths[i] = w; 
 
                if (i == to) { 
                    printPath(paths, to); 
                    break; 
                } 
            } 
        } 
    } 
} 

★另外，需要明白的是在沒有權(quán)重的圖中，廣度優(yōu)先搜索的結(jié)果就是最短路徑。這個是因為廣度優(yōu)先搜索的方式中，每次都是取最近的節(jié)點，那么當?shù)竭_終點時，其實所需次數(shù)是最少的。”

時間復(fù)雜度

廣度優(yōu)先搜索的時間復(fù)雜度最壞是遍歷整個圖，那么此時每個頂點都會被遍歷到，每條邊也會被訪問一次。那么，假設(shè)邊數(shù)為 E，頂點數(shù)為 V，此時時間復(fù)雜度為 O(V+E)(針對鄰接表來說)。

空間復(fù)雜度

廣度優(yōu)先搜索時，空間復(fù)雜度主要來自于隊列、visited 數(shù)組、paths 數(shù)組。這些數(shù)組的大小最大為 V，因為空間復(fù)雜度是 O(V)。

3.2. 深度優(yōu)先搜索(Depth-First-Search)

深度優(yōu)先搜索，簡稱 DFS。怎么直觀的理解呢?就是你從一個頂點出發(fā)，假如這個頂點有未被訪問過的頂點則訪問它，然后一個一個這么套下去。當一個頂點的相鄰頂點都被訪問過了，那么則退回上一個頂點，然后看一下上一個頂點是否有未被訪問過的鄰接頂點，有的話則訪問它，然后一層一層下去。如果也都被訪問過了，那么則再退。一個典型的生活中的例子就是走迷宮，先一條道走到“黑”，然后看不到出口了，上一個分叉口再換條道。

如圖所示，這是在圖上采用深度優(yōu)先搜索之后的樣子，實現(xiàn)表示搜索方向，虛線表示回退。

深度優(yōu)先搜索采用的思想是回溯思想，這種思想比較適合使用遞歸。我們使用遞歸的方式實現(xiàn)一下 DFS。相比 BFS，DFS 多了一個 find 變量，這個變量用于判斷是否有找到頂點的。如果在沒有遍歷到一個頂點的最后一個鄰接頂點之前就找到了終點，那么接下去的鄰接頂點就可以不用遍歷了，直接返回即可。

public void dfsSearch(int from, int to) { 
    if (this.v == 0 || from == to) { 
        return; 
    } 
 
    boolean[] visited = new boolean[this.v]; 
    int[] paths = new int[this.v]; 
    for (int i = 0; i < this.v; i++) { 
        visited[i] = false; 
        paths[i] = -1; 
    } 
 
    visited[from] = true; 
    reDFSS(from, to, visited, paths); 
 
    if (this.FIND_DFS == true) { 
        printPath(paths, to); 
    } 
} 
 
public void reDFSS(int from, int to, boolean[] visited, int[] paths) { 
 
    if (from == to) { 
        this.FIND_DFS = true;  
        return; 
    } 
 
    for (Integer i : this.adj[from]) { 
        if (this.FIND_DFS) { 
            return; 
        } 
        if (!visited[i]) { 
            visited[i] = true; 
            paths[i] = from; 
 
            reDFSS(i, to, visited, paths); 
        } 
    } 
} 

除了使用遞歸的方式實現(xiàn)之外，還可以將遞歸的方式轉(zhuǎn)化成棧和循環(huán)結(jié)合的方式。在圖的遍歷這小節(jié)內(nèi)容，你會看到非遞歸的方式。

★深度優(yōu)先搜索找到的并不是最短路徑。”

時間復(fù)雜度

采用同樣的方法，從頂點和邊的被訪問次數(shù)出發(fā)，每條邊最多被兩次訪問(一次遍歷，一次回退)，每個頂點被訪問一次，那么時間復(fù)雜度是 O(V+E)(針對鄰接表來說)。

空間復(fù)雜度

同樣的，深度優(yōu)先搜索的方式的空間復(fù)雜度主要來源棧、visited 數(shù)組和 paths 數(shù)組，棧的長度不可能超過頂點的個數(shù)，因此空間復(fù)雜度還是 O(V)。

3.3. 總結(jié)

1. 廣度和深度相比其他高級搜索算法(比如 A*算法)更簡單粗暴，沒有什么優(yōu)化，也被稱為暴力搜索算法。這兩種算法適用于圖不大的情況。
2. 深度優(yōu)先搜索主要借助了棧的方式，這個?？梢允呛瘮?shù)調(diào)用棧也可以是棧這種數(shù)據(jù)結(jié)構(gòu)(因為遞歸也可以轉(zhuǎn)化為非遞歸的方式)。廣度優(yōu)先搜索主要使用隊列。
3. 圖和樹的比較，圖的 DFS 類似于樹的先序遍歷;BFS 類似于樹的層次遍歷。
4. 在沒有權(quán)重的圖中，BFS 搜索的路徑結(jié)果就是最短路徑;DFS 搜索的結(jié)果卻不一定，因為 DFS 會“繞來繞去”，而 BFS 很直接每次都是最近的。
5. 在求圖的時間復(fù)雜度時，常用的方法是從頂點和邊被遍歷的次數(shù)出發(fā)。

4. 圖的遍歷

與圖的搜索算法有點不同的是，圖的遍歷是指將圖中的所有點都遍歷一次。常見的遍歷方法有深度優(yōu)先遍歷和廣度優(yōu)先遍歷。這兩種遍歷方法的思想還是一樣的，簡單來說就是圖的搜索方法就是加了一個節(jié)點判斷，如果找到相應(yīng)的節(jié)點就停止搜索。下面直接給出相應(yīng)的代碼，不再贅述。

4.1. 廣度優(yōu)先遍歷

public void bfsTraversal() { 
    if (this.v == 0) { 
        return; 
    } 
 
    boolean[] visited = new boolean[this.v]; 
    for (int i = 0; i < this.v; i++) { 
        visited[i] = false; 
    } 
    Queue<Integer> queue = new LinkedList<>(); 
    queue.offer(0); 
    visited[0] = true; 
 
    while (!queue.isEmpty()) { 
        int w = queue.poll(); 
        System.out.print(w + "\t"); 
 
        for (Integer i : this.adj[w]) { 
            if (visited[i] == false) { 
                queue.offer(i); 
                visited[i] = true; 
            } 
        } 
    } 
} 

4.2. 深度優(yōu)先遍歷

// 遞歸的方式 
public void dfsTraversal() { 
    if (this.v == 0) { 
        return; 
    } 
 
    boolean[] visited = new boolean[this.v]; 
    for (int i = 0; i < this.v; i++) { 
        visited[i] = false; 
    } 
 
    for (int i = 0; i < this.v; i++) { 
        if (!visited[i]) { 
            reDFST(i, visited); 
        } 
    } 
} 
 
public void reDFST(int f, boolean[] visited) { 
 
    visited[f] = true; 
    System.out.print(f + "\t"); 
    for (Integer i : this.adj[f]) { 
        if(!visited[i]) { 
            reDFST(i, visited); 
        } 
    } 
} 

// 非遞歸的方式，使用了棧 
public void dfsTraversalStack() { 
    if (this.v == 0) { 
        return; 
    } 
 
    boolean[] visited = new boolean[this.v]; 
    for (int i = 0; i < this.v; i++) { 
        visited[i] = false; 
    } 
 
    Stack<Integer> stack = new Stack<>(); 
    stack.push(0); 
    visited[0] = true; 
    System.out.print(0 + "\t"); 
 
    while (!stack.isEmpty()) { 
        int w = stack.peek(); 
        int flag = 0; 
        for (Integer i : this.adj[w]) { 
            if (!visited[i]) { 
                stack.push(i); 
                visited[i] = true; 
                System.out.print(i + "\t"); 
                flag = 1; 
                break; 
            } 
        } 
        if (flag == 0) { 
            stack.pop(); 
        } 
    } 
} 

本文轉(zhuǎn)載自微信公眾號「多選參數(shù)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系多選參數(shù)公眾號。