從零開始的圖論講解(1)——圖的概念,圖的存儲,圖的遍歷與圖的拓撲排序

前言

圖的概念

1. 頂點和邊

2. 圖的分類

3. 圖的基本性質

圖的存儲

鄰接矩陣存圖

鄰接表存圖

圖的基本遍歷

拓撲排序

拓撲排序是如何寫的呢?

1. 統計每個節點的入度

2. 構建鄰接表

3. 將所有入度為 0 的節點加入隊列

4. 不斷彈出隊頭節點，更新其相鄰節點的入度

5. 判斷是否存在環

結尾:

前言

本文將從最基礎的概念講起，介紹 圖的存儲方式和怎么遍歷圖(BFS和DFS基本遍歷)，并深入 拓撲排序及其應用，幫助你快速入門圖論。目標是讓你在短時間內掌握圖論的核心知識，并具備獨立完成 LeetCode 簡單及以上難度的圖論題目的能力。博客很長,歡迎大家根據目錄各取所需.

這是該系列的第一篇,在后面的博客中,筆者還會講解 最短路徑問題（Dijkstra、Bellman-Ford、SPFA） 和 最小生成樹（Kruskal、Prim） 等常見算法，幫助你建立圖論基礎。

筆者自知水平有限,?本博客的質量無法與專業算法書籍相比。但筆者希望通過 通俗易懂的語言，并結合 數據模擬，幫助零基礎的讀者快速入門圖論，并熟悉常見的圖論算法模板。對于需要復習的有基礎的讀者,也可以把該系列博客當成"模板代碼托管所",隨時備你復習!

目標是讓你 不僅能理解算法，還能夠在實際中熟練運用，讓圖論不再只是抽象的概念，而是可以直觀感受到的計算過程。?

圖論是計算機科學中的重要分支，在路徑規劃、網絡流分析、任務調度等多個領域有著廣泛應用,學好它對于我們提升代碼能力和使用數據結構的能力很有幫助。

好了,前言到此為止,希望您懷揣耐心讀下去

博客中出現的參考圖都是筆者手畫的,代碼示例也是筆者手敲的!影響雖小,但請勿抄襲

圖的概念

話不多說，首先什么是圖？圖是由一組頂點（Vertex）和一組邊（Edge）組成的結構，通常用于表示事物之間的關系。比如，社交網絡中的人和他們之間的關系可以用圖來表示；城市之間的道路、交通網絡也可以用圖來建模。圖論研究的就是這些結構以及如何對圖進行操作和分析。

1. 頂點和邊

頂點（Vertex）：圖中的基本元素，表示對象或節點。比如，在社交網絡中，每個用戶可以看作一個頂點；在城市的道路網中，每個城市可以看作一個頂點。
邊（Edge）：表示頂點之間的連接關系，通常可以有方向性或者沒有方向性。每條邊都連接著兩個頂點。邊可以表示各種關系，比如朋友之間的關系、城市之間的道路等。

2. 圖的分類

圖的分類可以依據邊的方向性、邊的權重等多個方面來進行，常見的分類包括：

無向圖（Undirected Graph）：圖中的每條邊沒有方向，表示兩個頂點之間的關系是雙向的。例如，社交網絡中朋友關系就是一種無向圖關系。

有向圖（Directed Graph）：圖中的每條邊都有方向，即每條邊從一個頂點指向另一個頂點。例如，網頁之間的超鏈接就是一種有向圖關系。

加權圖（Weighted Graph）：圖中的邊有權重（權值），表示連接兩個頂點之間的代價或距離。例如，城市之間的道路距離或者交通時間。

3. 圖的基本性質

鄰接關系：在圖中，如果兩個頂點通過邊相連，就稱它們是鄰接的。對于無向圖，如果頂點 A 和頂點 B 之間有邊，則 A 和 B 是鄰接的；而對于有向圖，如果從頂點 A 到頂點 B 有一條邊，則稱 B 是 A 的鄰接頂點。
度（Degree）：頂點的度是與該頂點相連的邊的數量。對于無向圖，頂點的度是其鄰接邊的數目；對于有向圖，分為入度（指向該頂點的邊數）和出度（從該頂點出發的邊數）。請牢記這個概念,因為拓撲排序需要用到它.
連通性：如果圖中的每一對頂點都有路徑相連，則稱圖是連通的。無向圖中的連通性比有向圖更容易理解，因為無向圖中不區分邊的方向，只要兩個頂點之間存在路徑就視為連通。圖的連通性問題也是一個概念很大的問題,有很多分支,感興趣的讀者們可以自己去了解

圖的存儲

相信很多初學者在學習圖論時，會因為對數據結構理解不夠深入而感到困惑，尤其是在理解圖的存儲方式時可能會遇到不少困難。圖的存儲方式決定了我們如何在計算機中表示和操作圖，因此掌握它至關重要。如果你對數組、鏈表等基本數據結構還不太熟悉，不用擔心，在接下來的內容中，我會用通俗易懂的方式來講解不同的存儲方法，幫助你輕松理解它們的優缺點以及適用場景。

因為圖中既有節點,又有邊(節點與節點之間的關系)，因此，在圖的存儲中，只需要保存：節點和邊關系即可。節點保存比較簡單，只需要一段連續空間即可，那邊關系該怎么保存呢？

我們主要介紹那么兩種,第一種是鄰接矩陣,第二種是鄰接表,還有一種叫做鏈式前向星的結構,但是筆者不做介紹.

鄰接矩陣存圖

首先是鄰接矩陣,這是最簡單最好理解的存儲方法,適用于密度高的圖,如果用于稀疏圖,那么效果不如鄰接表

我們定義二維數組 graph[N][N] 來存圖.

如果圖是無向無權值圖,那么 graph[i][j] == 1 表示點 i 到點 j 有連通

同理表示點 j?到點 i?連通

如果圖是有向無權值圖,那么 graph[i][j] == 1 表示點 i 到點 j 有連通

graph[j][i] == 1 表示點 j?到點 i?有連通

如果兩點 a,b之間沒有邊相連,那么 grapg[a][b] = 0.

如果帶權值,二維數組的值就是兩點之間的權值,同樣分為無向圖與有向圖,二維數組的含義與上文同理

例如:

同理,如果矩陣有具體值,那么邊就有了權值,這里筆者就不畫圖了

鄰接表存圖

不知道各位讀者是否對鄰接表這個名字很熟悉?是的,之前在介紹哈希表時,筆者就已經介紹過鄰接表

[入門JAVA數據結構 JAVADS] 哈希表的初步介紹和代碼實現-CSDN博客

鄰接表的思想是：每個節點維護一個鏈表（或數組/列表），記錄它連接到的所有節點。對于有權圖，我們在記錄目標節點的同時，也記錄每條邊的權值。通俗的說,鄰接表就像一個“關系表”，它告訴我們：每個節點直接連接到哪些節點。我們通過這些關系就可以完整地表示出整個圖。

以無權有向圖為例，假設圖如下：

1 → 2  
1 → 3  
2 → 4

那么在鄰接表中,是這么被存儲的

若這是有權圖（比如邊的權值分別為 5、7、2），則可以這樣表示：

1: (2,5) → (3,7)  
2: (4,2)  
3:  
4:

那么,在JAVA語言中,我們用什么數據結構去組織和描述鄰接表呢?

通過圖示我們可以看到,這種數據結構要求?

能夠按“節點編號”快速訪問；

每個節點后面還要掛一串“與它相連的邊”。

顯然,我們可以這么寫

List<List<Edge>> graph = new ArrayList<>();

外層 List 的下標表示當前節點編號；

內層 List<Edge> 保存當前節點連接的所有邊（每條邊都有終點和權值）；

Edge 是我們自己定義的一個類，表示一條邊。

這三個結合起來,我們就可以有效的存儲圖了,第一層的List下標代表起點,第二層List<Edge>?是一個存儲Edge的鏈表,里面有終點坐標和權值,如果是無權圖也可以用

List<Integer>.

?你可以理解成是一個“數組 + 鏈表”的組合體，既能快速定位每個節點，又能靈活添加邊。

我們再定義一個Edge類

class Edge {int to;      // 目標節點編號int weight;  // 邊的權值Edge(int to, int weight) {this.to = to;this.weight = weight;}
}

舉個例子,有個圖如下所示:

1 → 2 (權值3)
1 → 3 (權值5)
2 → 4 (權值2)

他在鄰接表中就長這樣

graph[1] -> [(2, 3), (3, 5)]
graph[2] -> [(4, 2)]
graph[3] -> []
graph[4] -> []

我們寫一個代碼簡單構建一下?

int n = 4; // 4 個節點，從 1 開始編號
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());
}// 添加邊
graph.get(1).add(new Edge(2, 3));
graph.get(1).add(new Edge(3, 5));
graph.get(2).add(new Edge(4, 2));

值得注意的是,上述的例子都是單向圖的構建方法,?因為這只是存儲了起點和終點,有并不代表終點也可以通往起點,因此,如果是雙向圖,就要構建兩次

例如:? 假設 a 點和?b 點是雙邊互通的,那么就應該這么構建

graph.get(a).add(new Edge(b, w)); // a → b
graph.get(b).add(new Edge(a, w)); // b → a

看到這里的你，哪怕是一名剛剛接觸圖論的小白，相信也已經不再對“圖”這個概念感到陌生了。我們已經了解了圖的基本概念、常見分類，以及如何用鄰接表在 Java 中高效地存儲圖結構。

為了節省大家的閱讀時間成本，避免重復講解一些過于基礎、但實際中不太常用的內容，接下來的圖論部分，我們默認所有圖都使用鄰接表進行存儲。這種方式在實際中應用廣泛，簡單高效

圖的基本遍歷

圖的遍歷是圖論中的基本操作之一。無論你是在求連通塊、尋找路徑，還是在實現更復雜的圖算法（比如最短路徑、拓撲排序），都繞不開遍歷操作。

常見的圖遍歷方式有兩種：

DFS（深度優先搜索）
BFS（廣度優先搜索）

這兩種遍歷中DFS更強調一條路走到黑,而BFS是層層遞進的遍歷

以下是我給出的代碼

import java.util.*;public class GraphTraversal {static int n, m;static final int N = 505;static List<List<Edge>> graph = new ArrayList<>();static boolean[] vis = new boolean[N];// 定義一個邊的類 (u->v, 權值w)static class Edge {int v, w;Edge(int v, int w) {this.v = v;this.w = w;}}// 添加一條 u -> v, 權值為 w 的邊static void addEdge(int u, int v, int w) {graph.get(u).add(new Edge(v, w));}// BFS 遍歷static void BFS(int start) {Arrays.fill(vis,false);Queue<Integer> queue = new LinkedList<>();queue.offer(start);vis[start] = true;System.out.print("BFS :");System.out.print(start+" ");while(!queue.isEmpty()){int temp = queue.poll();for(Edge edge : graph.get(temp)){if(!vis[edge.v]){vis[edge.v] = true;queue.offer(edge.v);System.out.print(edge.v+" ");}}}}// DFS 遍歷static void DFS(int node){if(vis[node]){return;}System.out.print(node+" ");vis[node] = true;for(Edge x : graph.get(node)){if(!vis[x.v]){DFS(x.v);}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();// 提前創建 n+1 個 ArrayList，避免越界for (int i = 0; i <= n+1000; i++) {graph.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();addEdge(a, b, c);}scanner.close();// 從 1 號節點開始遍歷（你可以改成 0）BFS(1);Arrays.fill(vis, false); // 重新初始化 vis 數組System.out.print("DFS: ");DFS(1);System.out.println();}
}

分別是DFS遍歷和BFS遍歷,通過vis數據去判斷結點是否被遍歷過,代碼很簡單?

我們給一組示例,如圖所示:

我們分別通過DFS和BFS遍歷,默認1為起始點

結果如下:

可以看到:

在 BFS（廣度優先搜索）中，我們從節點 1 開始遍歷。由于 BFS 的特點是按層次逐層訪問圖的節點，因此它的遍歷過程是按照節點距離起點的“層數”來進行的。具體來說：

首先輸出起始節點 1，這是第一層。

然后訪問與 1 相鄰的節點 2 和 3，這就是第二層。

接著，訪問與 2 和 3 相鄰的節點 4、5，這是第三層。

最后，訪問與 4 和 5 相鄰的節點 6，這是第四層。

BFS 的核心在于通過隊列來保證節點是按照層次順序被訪問的。它總是先訪問當前層的所有節點，然后再訪問下一層的節點。因此，BFS 是“逐層”訪問的。

而 DFS（深度優先搜索）則不同，它的遍歷方式是“沿著一條路徑一直走到底，然后再回溯”。因此，它會先訪問某個節點的所有相鄰節點，直到不能再繼續為止，然后再回溯到上一個節點，繼續訪問其他未訪問的鄰接節點。

首先輸出起始節點 1。

然后，DFS 會優先選擇一個與 1 相鄰的節點進行深入。在這個例子中，它會先訪問節點 2。

接下來，DFS 會沿著節點 2 的相鄰節點繼續深入，直到沒有新的節點可以訪問。此時會回溯到節點 2，然后繼續訪問其他未訪問的相鄰節點。

然后回溯到節點 1，訪問與 1 相鄰的節點 3，并重復相同的過程，直到所有節點都被訪問。

我們來看一道例題:1971. 尋找圖中是否存在路徑 - 力扣（LeetCode）

這道題就要求我們去遍歷圖,來判斷是否聯通

首先我們構建鄰接表,然后去遍歷判斷

首先對于構建鄰接表,因為這道題是雙向無權圖,所以我們可以構建

? List<List<Integer>> graph = new ArrayList<>() 來存儲圖

BFS寫法:??

class Solution {public boolean validPath(int n, int[][] edges, int source, int destination) {List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i < n; i++){graph.add(new ArrayList<>());}for (int[] edge : edges) {int u = edge[0], v = edge[1];graph.get(u).add(v);graph.get(v).add(u);}boolean[] vis = new boolean[n];Queue<Integer> queue = new LinkedList<>();queue.offer(source);vis[source] = true;while(!queue.isEmpty()){int temp = queue.poll();if(temp == destination){return true;}for(Integer num : graph.get(temp)){if(!vis[num]){vis[num] = true;queue.offer(num);}}}return false;}
}

首先構建雙向鄰接表,然后遍歷

DFS寫法: 和上述同理

class Solution {static  boolean[] vis;public  boolean DFS(List<List<Integer>> graph,int st,int ed){if(st == ed){return true;}vis[st] = true;for(Integer num:graph.get(st)){if(!vis[num]){boolean pd = DFS(graph,num,ed);if(pd == true){return true;}}}return  false;}public boolean validPath(int n, int[][] edges, int source, int destination) {List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i < n; i++){graph.add(new ArrayList<>());}for (int[] edge : edges) {int u = edge[0], v = edge[1];graph.get(u).add(v);graph.get(v).add(u);}vis = new boolean[n];boolean pdf = DFS(graph,source,destination);return pdf==true?true:false;}
}

?當然,這不是該題的最優解法,但是我們可以通過這題了解BFS與DFS是如何遍歷圖的.

拓撲排序

?拓撲排序可以被看作是BFS,DFS的簡單應用,從代碼模板上看也是這樣的.

"拓撲排序"是圖論中一個非常經典的問題，常用于解決“有依賴關系的任務排序問題”。比如學習技術棧,如果我要成為一個合格的JAVA開發工程師,我需要學習很多技術棧

在學習 SpringBoot 之前，必須先掌握 JavaSE 和 JavaEE 的基礎；

在學習 MyBatis 前，需要具備一定的數據庫基礎，比如 SQL；

想要理解分布式系統，還得先了解網絡通信、RPC 原理、消息隊列等內容；

構建前后端分離項目，也依賴于對前端基礎、后端 API 編寫等知識的掌握。

但是拓撲排序的前提是圖必須是有向且無環的圖,如果圖中存在環，那么就無法構建出合法的拓撲序列 —— 比如課程 A 依賴課程 B，B 又依賴 A，這樣就永遠無法開始任何課程。

舉個例子:

它拓撲排序的結果應該是:

1 3 2 4 5 6??

拓撲排序是如何寫的呢?

大概有這么幾個步驟?

1. 統計每個節點的入度

每個節點的入度是指：有多少條邊指向它。我們需要用一個數組來記錄每個點的入度。這個在前面也提到了
   static  int []  ingrade;//存儲入度
    public  static  void addEdge(int u,int v){graph.get(u).add(v);// 表示 u 到 v 有一條邊ingrade[v]++;}
2. 構建鄰接表

我們用鄰接表來表示圖中每個節點的出邊（即它連接到哪些后續節點）：
       for(int i = 0;i<=n;i++){graph.add(new ArrayList<>());}for(int i = 0;i<m;i++){int a = scanner.nextInt();int b = scanner.nextInt();addEdge(a,b);}
3. 將所有入度為 0 的節點加入隊列

這些節點說明它們沒有前置依賴，可以作為起點。我們使用一個隊列來進行 BFS

4. 不斷彈出隊頭節點，更新其相鄰節點的入度

遍歷過程中，每訪問一個節點，就“移除”它的影響，也就是把它連接的邊都刪掉，同時更新這些目標節點的入度。

5. 判斷是否存在環

如果最終輸出的拓撲序列長度少于 n，說明存在環（即有任務間形成了“循環依賴”）
    public  static  void BFS(){PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();for(int i =1;i<=n;i++){if(ingrade[i]==0)//入度為0{priorityQueue.offer(i);}}while(!priorityQueue.isEmpty()){int node = priorityQueue.poll();result.add(node);for(Integer neighbor : graph.get(node)){ingrade[neighbor]--;//相鄰結點入度--if(ingrade[neighbor]==0){priorityQueue.add(neighbor);}}}}

完整代碼如下:

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
//拓撲排序是一種 用于有向無環圖（DAG，Directed Acyclic Graph） 的排序方法，它將圖中的所有節點排成一個線性序列，使得對于 每一條有向邊
//𝑢→𝑣,節點 u 在序列中出現在 v 之前。
public class TopoSortBFS
{static  int n,m;static List<List<Integer>> graph = new ArrayList<>(); // 用鄰接表存儲圖static List<Integer> result = new ArrayList<>();public  static  void addEdge(int u,int v){graph.get(u).add(v);// 表示 u 到 v 有一條邊ingrade[v]++;}public  static  void BFS(){PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();for(int i =1;i<=n;i++){if(ingrade[i]==0)//入度為0{priorityQueue.offer(i);}}while(!priorityQueue.isEmpty()){int node = priorityQueue.poll();result.add(node);for(Integer neighbor : graph.get(node)){ingrade[neighbor]--;//相鄰結點入度--if(ingrade[neighbor]==0){priorityQueue.add(neighbor);}}}}static  int []  ingrade;//存儲入度public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt(); // 讀取節點數m = scanner.nextInt(); // 讀取邊數ingrade = new int[n+1];for(int i = 0;i<=n;i++){graph.add(new ArrayList<>());}for(int i = 0;i<m;i++){int a = scanner.nextInt();int b = scanner.nextInt();addEdge(a,b);}BFS();if(result.size()==n){for(Integer i : result){System.out.print(i+" ");}}else{System.out.println(-1);}}
}

?我們可以看一道例題:0戀愛通關游戲 - 藍橋云課

在這個例題中，我們需要在一個無環圖（DAG）中，從起點出發，依次經歷多個關卡，根據不同選擇提升好感度，直到到達終點關卡，并判斷最終好感度是否達到目標值（≥100）。

從圖論的角度來看：

每個關卡可以看成是一個圖中的節點；

每個選項可以看成是有向邊，帶有一個權值（即好感度提升值）；

整個游戲流程構成了一張有向無環圖（DAG），因為題目明確說明“不會再遇到已結束關卡”，即不存在回環；

最終目標是從起點到某個終點路徑中，累積最大好感度，看是否能達到通關標準。

因此，這道題本質上就是在一張 DAG 上找最大路徑和 的問題。

?為什么是拓撲排序？

這是一個非常典型的拓撲排序應用場景：

只有當一個節點的所有前驅節點都已經被處理完，才能開始計算它的最優值。

換句話說，我們必須嘗試過所有能到達該節點的路徑，才能確定哪一條路徑帶來的值最大（或最小）。

所以，我們需要先對整個圖進行 拓撲排序，然后按照拓撲序去“刷新”每個點的最大好感度。

題解代碼:


import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.*;
public class Demo46 {// Edge 用于存邊，a->b好感度為c；b就是達到的關卡，c為好感度static class Node{int b, c;public Node(int b, int c){this.b = b; this.c = c;}}static final int N = (int)2e5+10;static int[] dis = new int[N]; // 用于存儲到達當前關卡的好感度 cArr[i]  表示到 i 點的好感度static  List<List<Node>> list = new ArrayList<>();static Queue<Integer> queue = new LinkedList<>(); // 入度為0的關卡加入到order列表中，以用于拓撲排序static int[] inDegree = new int[N]; // 記錄每個關卡的當前入度static  int res = 0;public static void addEdge(int a,int b,int c){list.get(a).add(new Node(b,c));inDegree[b]++;}public static void BFS() {Arrays.fill(dis, (int) -2e8);// 入度為 0 的點，初始化for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {queue.offer(i);dis[i] = 0;  // 所有入度為 0 的點，都要初始化為 0}}while (!queue.isEmpty()) {int st = queue.poll();// 終點判斷：出度為 0 的節點if (list.get(st).isEmpty() && dis[st] >= 100) {res++;}for (Node temp : list.get(st)) {int ed = temp.b;inDegree[ed]--;if (inDegree[ed] == 0) {queue.offer(ed);}dis[ed] = Math.max(dis[ed], dis[st] + temp.c);}}}static int n,m;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();for(int j = 0;j<=n;j++){list.add(new ArrayList<>());}while(m!=0){m--;int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();addEdge(a,b,c);}BFS();System.out.println(res);}
}