文章目錄

  • 圖論理論基礎（1）
  • 1. 圖的基本概念
  • 1.1 基本術語
  • 2. 圖的分類
  • 2.1 有向圖 vs 無向圖
  • 2.2 加權圖 vs 無權圖
  • 2.3 度（Degree）
  • 3. 圖的連通性
  • 3.1 連通圖 vs 非連通圖
  • 3.2 強連通性（有向圖）
  • 3.3 連通分量（無向圖）
  • 4. 圖的存儲方式
  • 4.1 鄰接矩陣
  • 4.2 鄰接表
  • 4.3 邊列表
  • 5. 圖的遍歷算法
  • 5.1 深度優先搜索（DFS）
  • 5.2 廣度優先搜索（BFS）
  • 6. 圖論算法分類
  • 6.1 圖的存儲與遍歷
  • 6.2 拓撲排序
  • 6.3 並查集
  • 6.4 最短路徑算法
  • 6.5 最小生成樹
  • 7. 時間複雜度總結
  • 8. DFS與BFS對比
  • 8.1 算法對比
  • 8.2 DFS搜索過程
  • 8.3 DFS代碼框架
  • 9. BFS詳解
  • 9.1 BFS使用場景
  • 9.2 BFS搜索過程
  • 9.3 BFS代碼框架

圖論理論基礎（1）

1. 圖的基本概念

**圖（Graph）**是由頂點（Vertex/Node）和邊（Edge）組成的數據結構，用來表示事物之間的關係。

1.1 基本術語

  • 頂點（Vertex）：圖中的節點，表示事物
  • 邊（Edge）：連接兩個頂點的線，表示關係
  • 路徑（Path）：從一個頂點到另一個頂點經過的邊的序列
  • 環（Cycle）：起點和終點相同的路徑

2. 圖的分類

2.1 有向圖 vs 無向圖

  • 無向圖：邊沒有方向，A-B 和 B-A 是同一條邊
  • 有向圖：邊有方向，A→B 和 B→A 是不同的邊

2.2 加權圖 vs 無權圖

  • 無權圖：邊沒有權重，只表示連接關係
  • 加權圖：邊有權重，表示距離、成本等

2.3 度（Degree）

  • 度：與頂點相連的邊的數量
  • 出度：有向圖中從頂點出發的邊的數量
  • 入度：有向圖中指向頂點的邊的數量

3. 圖的連通性

3.1 連通圖 vs 非連通圖

  • 連通圖：任意兩個頂點之間都存在路徑
  • 非連通圖：存在兩個頂點之間沒有路徑

3.2 強連通性（有向圖）

  • 強連通圖：任意兩個頂點之間都存在雙向路徑
  • 強連通分量：極大強連通子圖

示例：

有向圖：A → B → C → A
        ↓
        D

強連通分量1：{A, B, C} - 這三個節點互相可達
強連通分量2：{D} - 單獨一個節點

圖解：

A ──→ B ──→ C
│           │
│           │
└───────────┘
│
↓
D

3.3 連通分量（無向圖）

  • 連通分量：無向圖中的極大連通子圖
  • 連通分量數量：圖中連通分量的個數

示例：

無向圖：A-B-C, D-E, F

連通分量1：{A, B, C} - 這三個節點互相連通
連通分量2：{D, E} - 這兩個節點互相連通  
連通分量3：{F} - 單獨一個節點
連通分量數量：3

圖解：

A ── B ── C    D ── E    F

4. 圖的存儲方式

4.1 鄰接矩陣

// 適合稠密圖，空間複雜度O(V²)
vector<vector<int>> graph(V, vector<int>(V, 0));
// graph[i][j] = 1 表示頂點i和j之間有邊

4.2 鄰接表

// 適合稀疏圖，空間複雜度O(V+E)
vector<vector<int>> graph(V);
// graph[i] 存儲與頂點i相鄰的所有頂點

4.3 邊列表

// 存儲所有邊的信息
vector<pair<int, int>> edges;  // 無權邊
vector<tuple<int, int, int>> edges;  // 加權邊 (u, v, weight)

5. 圖的遍歷算法

5.1 深度優先搜索（DFS）

算法特點：

  • 深度優先：儘可能深地搜索圖的分支
  • 遞歸實現：使用遞歸棧，代碼簡潔
  • 應用場景：路徑查找、連通性判斷、拓撲排序
  • 時間複雜度：O(V+E)，每個頂點和邊訪問一次
  • 空間複雜度：O(V)，遞歸棧的深度

執行過程示例：

圖：A-B-C
    |   |
    D   E

DFS訪問順序：A → B → C → E → D

代碼實現：

void dfs(int node, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[node] = true;  // 標記當前節點已訪問
    
    // 遍歷當前節點的所有鄰居
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 如果鄰居未被訪問
            dfs(neighbor, visited, graph);  // 遞歸訪問鄰居
        }
    }
}

5.2 廣度優先搜索（BFS）

算法特點：

  • 廣度優先：逐層訪問，先訪問距離近的節點
  • 隊列實現：使用隊列維護訪問順序
  • 應用場景：最短路徑、層次遍歷、連通性判斷
  • 時間複雜度：O(V+E)，每個頂點和邊訪問一次
  • 空間複雜度：O(V)，隊列的最大長度

執行過程示例：

圖：A-B-C
    |   |
    D   E

BFS訪問順序：A → B → D → C → E
層次：第0層：A
     第1層：B, D
     第2層：C, E

代碼實現：

void bfs(int start, vector<vector<int>>& graph) {
    queue<int> q;  // 隊列存儲待訪問的節點
    vector<bool> visited(graph.size(), false);  // 標記數組
    
    q.push(start);  // 將起始節點加入隊列
    visited[start] = true;  // 標記起始節點已訪問
    
    while (!q.empty()) {  // 隊列不為空時繼續
        int node = q.front();  // 取出隊首節點
        q.pop();  // 從隊列中移除
        
        // 遍歷當前節點的所有鄰居
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {  // 如果鄰居未被訪問
                visited[neighbor] = true;  // 標記鄰居已訪問
                q.push(neighbor);  // 將鄰居加入隊列
            }
        }
    }
}

6. 圖論算法分類

6.1 圖的存儲與遍歷

  • DFS/BFS：基礎遍歷算法
  • 應用：島嶼數量、被圍繞的區域

6.2 拓撲排序

  • Kahn算法：基於入度的拓撲排序
  • DFS法：基於深度優先搜索的拓撲排序
  • 應用：課程表、任務調度

6.3 並查集

  • Union-Find：集合合併與查詢
  • 應用：省份數量、朋友圈

6.4 最短路徑算法

  • Dijkstra：單源最短路徑（非負權）
  • Bellman-Ford：單源最短路徑（可處理負權）
  • Floyd-Warshall：多源最短路徑

6.5 最小生成樹

  • Kruskal：基於邊的貪心算法
  • Prim：基於頂點的貪心算法

7. 時間複雜度總結

算法

時間複雜度

空間複雜度

適用場景

DFS/BFS

O(V+E)

O(V)

圖遍歷

拓撲排序

O(V+E)

O(V)

DAG排序

並查集

O(α(n))

O(V)

連通性判斷

Dijkstra

O((V+E)logV)

O(V)

單源最短路

Floyd

O(V³)

O(V²)

多源最短路

Kruskal

O(ElogE)

O(V)

最小生成樹

8. DFS與BFS對比

8.1 算法對比

比較項

DFS（深度優先搜索）

BFS（廣度優先搜索）

搜索策略

一條路走到黑（遞歸/棧）

一層一層擴展（隊列）

實現方式

通常用 遞歸 或 顯式棧

通常用 隊列（queue）

適用場景

適合 全路徑搜索、組合問題、回溯問題（如圖遍歷、排列組合）

適合 最短路徑問題、層次遍歷（如最短步數、層數搜索）

空間複雜度

相對較小（與遞歸深度有關）

相對較大（需存整層節點）

典型應用

迷宮求解、圖連通分量、全排列

最短路徑、最少步數、層序遍歷

8.2 DFS搜索過程

假設你在一個迷宮中：

  1. 看到一個路口 → 選一條路走；
  2. 走到底發現死路 → 返回上一個岔口；
  3. 選另一條沒走過的路 → 再次深入；
  4. 最終找到所有可能的出口。

這整個過程就叫 深度優先搜索（DFS）。

8.3 DFS代碼框架

vector<vector<int>> result; // 保存符合條件的所有路徑
vector<int> path; // 起點到終點的路徑

void dfs (參數){
    if (終止條件) {
        存放結果;
        return;
    }

    for (選擇：本節點所連接的其他節點) {
        處理節點;
        dfs(圖，選擇的節點); // 遞歸
        回溯，撤銷處理結果
    }
}

9. BFS詳解

9.1 BFS使用場景

廣度優先搜索（Breadth First Search，簡稱 BFS）是一種逐層搜索的算法，常用於在圖或樹結構中尋找最短路徑或最小步數的問題。

常見使用場景：

  1. 最短路徑問題：
    例如在無權圖中，尋找從起點到終點的最短路徑。
  • 典型例題：二叉樹的最短深度、迷宮最短路徑、網絡中最短連接。
  1. 層序遍歷：
    BFS 天然按層擴展節點，因此在樹結構中可用於層序遍歷。
  2. 狀態搜索類問題：
    如八數碼問題、單詞接龍、棋盤問題等，BFS 可用於尋找最少操作次數。
  3. 網絡流與最短增廣路：
    在最大流算法（如 Edmonds-Karp）中，BFS 用於尋找最短增廣路徑。
  4. 多源最短路問題：
    同時從多個起點出發，計算所有點到最近起點的最短距離。

9.2 BFS搜索過程

BFS 採用隊列（queue）實現“先進先出”的搜索邏輯，從起點開始，依次訪問相鄰節點，逐層向外擴展。

搜索流程：

  1. 將起點加入隊列，並標記為已訪問；
  2. 當隊列非空時：
  • 取出隊首節點；
  • 遍歷該節點的所有鄰接節點；
  • 若鄰接節點未訪問，則加入隊列並標記；
  1. 直到隊列為空或找到目標。

9.3 BFS代碼框架

int dir[4][2] = {
    {0, 1}, {1, 0}, {0, -1}, {-1, 0}
};// 表示四個方向
// grid 是地圖，也就是一個二維數組
// visited標記訪問過的節點，不要重複訪問
// x,y 表示開始搜索節點的下標
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定義隊列
    que.push({x, y}); // 起始節點加入隊列
    visited[x][y] = true; // 只要加入隊列，立刻標記為訪問過的節點
    //加入隊列就代表 走過，就需要標記，而不是從隊列拿出來的時候再去標記走過。要不然會導致很多重複
    while(!que.empty()) { // 開始遍歷隊列裏的元素
        pair<int ,int> cur = que.front(); que.pop(); // 從隊列取元素
        int curx = cur.first;
        int cury = cur.second; // 當前節點座標
        for (int i = 0; i < 4; i++) { // 開始想當前節點的四個方向左右上下去遍歷
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 獲取周邊四個方向的座標
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 座標越界了，直接跳過
            if (!visited[nextx][nexty]) { // 如果節點沒被訪問過
                que.push({nextx, nexty});  // 隊列添加該節點為下一輪要遍歷的節點
                visited[nextx][nexty] = true; // 只要加入隊列立刻標記，避免重複訪問
            }
        }
    }

}