關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers

圖的基本概念

• 頂點（Vertex） 與 邊（Edge）
• 圖的表示： 鄰接表 和 鄰接矩陣
  • 這里可以分為 有向圖 和無向圖
  • 有權(quán)圖 和 無權(quán)圖
• 圖的遍歷：
  • DFS
  • BFS
  • 常見可以解決的問題有： 聯(lián)通分量，F(xiàn)lood Fill，尋路，走迷宮，迷宮生成，無權(quán)圖的最短路徑，環(huán)的判斷
• 最小生成樹問題（Minimum Spanning Tree）：Prim，Kruskal
• 最短路徑問題（Shortest Path）：Dijkstra，Bellman-Ford
• 拓撲排序（Topological sorting）

頂點的度

• 無向圖：頂點的度表示以該頂點作為一個端點的邊的數(shù)目。
• 有向圖：頂點的度分為入度和出度：
  • 入度表示以該頂點為終點的入邊數(shù)目
  • 出度是以該頂點為起點的出邊數(shù)目
  • 該頂點的度等于其入度和出度之和

不管是無向圖還是有向圖，頂點數(shù) n，邊數(shù) e 和頂點的度數(shù) D(Vi)有如下關(guān)系：
e = 1/2 *(D(v1) + D(v2) + ... + D(vn))

路徑、路徑長度和回路

路徑：比如在無向圖 G 中，存在一個頂點序列 Vp，Vi1，Vi2，Vi3 …，Vim，Vq，使得(Vp,Vi1)，(Vi1,Vi2)，…，(Vim,Vq)均屬于邊集 E(G) ，則稱頂點 Vp 到 Vq 存在一條路徑。

路徑長度：是指一條路徑上經(jīng)過的邊的數(shù)量。

回路：指一條路徑的起點和終點為同一個頂點。

圖的存儲結(jié)構(gòu)（表示圖）

一個圖結(jié)構(gòu)

邊的集合 Edge lists

To represent an edge, we just have an array of two vertex numbers, or an array of objects containing the vertex numbers of the vertices that the edges are incident on. 無權(quán)圖可以使用二元組 <Vp, Vq>
If edges have weights, add either a third element to the array or more information to the object, giving the edge's weight. 無權(quán)圖可以使用三元組 <Vp, Vq, weight>

例如：[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]

鄰接矩陣 Adjacency matrices

使用一個二維數(shù)組 adj[][]，如果頂點 i 和 頂點 j 之間有邊，則 adj[i][j] = 1 or weight

鄰接矩陣

鄰接表 Adjacency lists

鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。這種存儲結(jié)構(gòu)類似于樹的孩子鏈表。
對于圖 G 中每個頂點 Vi，把所有鄰接于 Vi 的頂點 Vj 鏈成一個單鏈表，這個單鏈表稱為頂點 Vi 的鄰接表。

鄰接表

圖的兩種遍歷方法

深度優(yōu)先搜索遍歷 DFS

• 假設(shè)初始狀態(tài)是圖中所有頂點都未曾訪問過，則可從圖 G 中任意一頂點 v 為初始出發(fā)點，首先訪問出發(fā)點 v，并將其標記為已訪問過
• 然后依次從 v 出發(fā)搜索v的每個鄰接點 w，若 w 未曾訪問過，則以 w 作為新的出發(fā)點出發(fā)，繼續(xù)進行深度優(yōu)先遍歷，直到圖中所有和 v 有路徑相通的頂點都被訪問到
• 若此時圖中仍有頂點未被訪問，則另選一個未曾訪問的頂點作為起點，重復上述步驟，直到圖中所有頂點都被訪問到為止

簡單的來說，深度優(yōu)先搜索包括從一條路徑的起始點開始追溯，直到到達最后一個頂點，然后回溯，繼續(xù)追溯下一條路徑，直到到達最后的頂點，如此往復，直到?jīng)]有路徑為止。

如果采用鄰接矩陣存儲，則時間復雜度為 O(n^2)；當采用鄰接表時時間復雜度為 O(n + e)。

代碼如下：

// 記錄每個頂點是否被訪問過
boolean visited[] = new boolean[V];

// 從編號為 s 的頂點開始做深度優(yōu)先遍歷
void DFS(int s)
{
    // 首先訪問出發(fā)點
    visited[s] = true;
    System.out.print(v + " ");

    // 接著依次訪問 s 的所有未被訪問過的鄰接點并均標記為已訪問過
    for(each node i which are adjacence of s)
    {
        if (!visited[i]) {
            DFS(i);
        }
    }
}

廣度優(yōu)先搜索遍歷 BFS

• 首先訪問出發(fā)點 Vi
• 接著依次訪問 Vi 的所有未被訪問過的鄰接點 Vi1，Vi2，Vi3，…，Vit 并均標記為已訪問過
• 然后再按照 Vi1，Vi2，Vi3，…，Vit 的次序，訪問每一個頂點的所有未曾訪問過的頂點并均標記為已訪問過，依此類推，直到圖中所有和初始出發(fā)點 Vi 有路徑相通的頂點都被訪問過為止

簡單的來說，廣度優(yōu)先搜索從一個頂點開始，嘗試訪問盡可能靠近它的頂點。本質(zhì)上這種搜索在圖上是逐層移動的，首先檢查最靠近第一個頂點的層，再逐漸向下移動到離起始頂點最遠的層。

如果采用鄰接矩陣存儲，則時間復雜度為 O(n^2)；當采用鄰接表時時間復雜度為 O(n + e)。

代碼如下：

// 從編號為 s 的頂點開始做廣度優(yōu)先遍歷
void BFS(int s)
{
    // 記錄每個頂點是否被訪問過
    boolean visited[] = new boolean[V];

    // 使用隊列
    LinkedList<Integer> queue = new LinkedList<Integer>();

    // 首先訪問出發(fā)點
    visited[s] = true;
    queue.add(s);

    while (!queue.isEmpty())
    {
        s = queue.poll();
        System.out.print(s + " ");

        // 接著依次訪問 s 的所有未被訪問過的鄰接點并均標記為已訪問過
        for(each node i which are adjacence of s)
        {
            if (!visited[i])
            {
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}

查找最短路徑

廣度優(yōu)先搜索對應的最短路徑
在執(zhí)行廣度優(yōu)先搜索時，會自動查找從一個頂點到另一個相鄰頂點的最短路徑。
例如：要查找從頂點 A 到頂點 D 的最短路徑，我們首先會查找從 A 到 D 是否有任何一條單邊路徑，接著查找兩條邊的路徑，以此類推，這正是廣度優(yōu)先搜索的搜索過程。

LeetCode題目：743. Network Delay Time
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

代碼如下：Dijkstra 算法

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        if (times == null || times.length == 0 || times[0].length == 0) {
            return -1;
        }
        
        // 使用鄰接矩陣 Adjacency matrices 存儲圖結(jié)構(gòu)
        int[][] adj = new int[N + 1][N + 1];
        for (int[] arr : adj) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }
        
        // 有權(quán)圖
        for (int[] edge : times) {
            adj[edge[0]][edge[1]] = edge[2];
        }

        // res[i] 表示頂點 K 到頂點 i 的時間
        int[] res = new int[N + 1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[K] = 0;
        
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(K);
        
        while (!queue.isEmpty()) {
            Integer start = queue.poll();
            
            for (int i = 1; i <= N; i++) {
                int weight = adj[start][i];
                
                // DP 動態(tài)規(guī)劃
                if (weight != Integer.MAX_VALUE && res[i] > res[start] + weight) {
                    res[i] = res[start] + weight;
                    queue.offer(i);
                }
            }
        }
        
        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (res[i] == Integer.MAX_VALUE) {
                return -1;
            }
            
            count = Math.max(count, res[i]);
        }
        
        return count;
    }
}

拓撲排序

在圖論中，拓撲排序（Topological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。
該序列必須滿足下面兩個條件：

• 每個頂點出現(xiàn)且只出現(xiàn)一次
• 若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面

注意：

• 有向無環(huán)圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說
• 通常，一個有向無環(huán)圖可以有一個或多個拓撲排序序列

拓撲排序通常用來“排序”具有依賴關(guān)系的任務(wù)。它與廣度優(yōu)先搜索BFS類似。
不同的是，拓撲排序算法不會立即輸出已訪問的頂點，而是訪問當前頂點鄰接表中的所有相鄰頂點，直到這個列表窮盡時，才將當前頂點壓入棧中。

基本過程：

• 從 DAG 圖中選擇一個 沒有前驅(qū)（即入度為0）的頂點并輸出。
• 從圖中刪除該頂點和所有以它為起點的有向邊。
• 重復以上步驟直到當前的 DAG 圖為空或當前圖中不存在無前驅(qū)的頂點為止。

LeetCode題目：207. Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 將 Edge lists 轉(zhuǎn)化為 鄰接矩陣 Adjacency matrices
        int[][] adj = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses];
        
        // 構(gòu)造一個有向圖
        for(int[] edge : prerequisites) {
            // p 依賴于 q
            int p = edge[0];
            int q = edge[1];
            
            // 防止重復輸入同樣的邊
            if(adj[q][p] == 0)
                indegree[p]++;
            
            adj[q][p] = 1;
        }
        
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for(int i = 0; i < numCourses; i++) {
            // 從 DAG 圖中選擇一個 沒有前驅(qū)（即入度為0）的頂點并輸出
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int i = queue.poll();
            
            count++;
            
            // 從圖中刪除該頂點和所有以它為起點的有向邊
            for(int j = 0; j < numCourses; j++) {
                if(adj[i][j] == 1) {
                    adj[i][j] = 0;
                    indegree[j]--;
                    
                    // 重復以上步驟直到當前的 DAG 圖為空或當前圖中不存在無前驅(qū)的頂點為止
                    if(indegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
        
        return count == numCourses;
    }
}

LeetCode題目：210. Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
        
        // 將 Edge lists 轉(zhuǎn)化為 鄰接矩陣 Adjacency matrices
        int[][] adj = new int[numCourses][numCourses];
        int[] indegree = new int[numCourses];
        
        // 構(gòu)造一個有向圖
        for(int[] edge : prerequisites) {
            // p 依賴于 q
            int p = edge[0];
            int q = edge[1];
            
            // 防止重復輸入同樣的邊
            if(adj[q][p] == 0)
                indegree[p]++;
            
            adj[q][p] = 1;
        }
        
        int count = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for(int i = 0; i < numCourses; i++) {
            // 從 DAG 圖中選擇一個 沒有前驅(qū)（即入度為0）的頂點并輸出
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int i = queue.poll();
            
            result[count] = i;
            
            count++;
            
            // 從圖中刪除該頂點和所有以它為起點的有向邊
            for(int j = 0; j < numCourses; j++) {
                if(adj[i][j] == 1) {
                    adj[i][j] = 0;
                    indegree[j]--;
                    
                    // 重復以上步驟直到當前的 DAG 圖為空或當前圖中不存在無前驅(qū)的頂點為止
                    if(indegree[j] == 0) {
                        queue.offer(j);
                    }
                }
            }
        }
        
        return count == numCourses ? result : (new int[0]);
    }
}

最小生成樹

給定一個無方向的帶權(quán)圖 G=(V, E)，最小生成樹為集合 T，T 是以最小代價連接 V 中所有頂點所用邊E的最小集合。集合 T 中的邊能夠形成一顆樹，這是因為每個節(jié)點（除了根節(jié)點）都能向上找到它的一個父節(jié)點。它包含全部 n 個頂點及 n - 1 條邊。

Kruskal 算法

此算法可以稱為 “加邊法”，初始最小生成樹邊數(shù)為0，每迭代一次就選擇一條滿足條件的最小代價邊，加入到最小生成樹的邊集合里。

• 把圖中的所有邊按代價從小到大排序；
• 把圖中的 n 個頂點看成獨立的 n 棵樹組成的森林；
• 按權(quán)值從小到大選擇邊，所選的邊連接的兩個頂點 ui，vi 應屬于兩顆不同的樹，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹。
• 重復上述步驟，直到所有頂點都在一顆樹內(nèi)或者有 n-1 條邊為止。

如圖所示：

Kruskal 算法

Prime 算法

此算法可以稱為 “加點法”，每次迭代選擇代價最小的邊對應的點，加入到最小生成樹中。算法從某一個頂點 s 開始，逐漸長大覆蓋整個連通網(wǎng)的所有頂點。

• 圖的所有頂點集合為 V；初始令集合 u = {s}，v = V?u;
• 在兩個集合u，v能夠組成的邊中，選擇一條代價最小的邊 (u0, v0)，加入到最小生成樹中，并把 v0 并入到集合 u 中。
• 重復上述步驟，直到所有頂點都在一顆樹內(nèi)或者有 n-1 條邊為止。

如圖所示：

Prime 算法

引用：
數(shù)據(jù)結(jié)構(gòu)與算法：圖和圖算法(一)
Representing graphs
圖的基本算法（最小生成樹）
算法導論--最小生成樹（Kruskal和Prim算法）