[Data Structure] 圖

圖 (Graph) 是一種非線性資料結構，由頂點 (Vertex， $V$ ) 與邊 (Edge， $E$ ) 組成，描述物件之間的關係，是資料結構中表達能力最強的一種。後面常用 $|V|$ 代表頂點數、 $|E|$ 代表邊數。

應用範例：捷運路線圖、社群媒體好友關係、Google Maps 導航路徑、電腦網路連線拓樸。

樹其實是圖的一種特例——「無環的連通圖」。兩者最大的差別在於：樹有嚴格的層次結構（只能由父節點連向子節點，不能形成環），而圖的邊沒有這些限制，節點之間可以任意相連、形成環，也可以彼此不相連。

術語

術語	英文	說明
頂點	Vertex	圖中每一個資料單元
邊	Edge	連接兩個頂點的線
相鄰	Adjacent	兩個頂點之間有邊相連
度	Degree	某頂點連接的邊數
路徑	Path	從某頂點到另一頂點，經過一連串邊所形成的序列
環	Cycle	路徑的起點與終點相同
連通圖	Connected Graph	圖中任意兩個頂點之間都存在路徑

圖的分類

無向圖 vs 有向圖

最基本的分類是依照邊是否有方向性：

無向圖 (Undirected Graph)：邊沒有方向，A 連 B 代表雙向可通行
有向圖 (Directed Graph / Digraph)：邊有方向，A → B 不代表 B → A

以下左右並列同一組點，對照邊「有沒有箭頭」造成的差異：

在程式建立圖時，差別只在 addEdge 是否雙向設定：

// 無向圖：兩個方向都設定
static void addEdge(int[][] matrix, int u, int v) {
    matrix[u][v] = 1;
    matrix[v][u] = 1;
}

// 有向圖：只設定 u → v 單一方向
static void addEdge(int[][] matrix, int u, int v) {
    matrix[u][v] = 1;
}

鄰接串列的有向圖寫法同理：

// 無向圖
static void addEdge(Map<Integer, List<Integer>> graph, int u, int v) {
    graph.get(u).add(v);
    graph.get(v).add(u);
}

// 有向圖：只把 v 加入 u 的串列
static void addEdge(Map<Integer, List<Integer>> graph, int u, int v) {
    graph.get(u).add(v);
}

有權圖 (Weighted Graph)

邊上帶有數值（權重 Weight），通常代表距離、成本或時間。典型應用：Google Maps 導航——演算法找出總權重最小的路徑。

圖的表示方式

兩種主流方式：

鄰接矩陣 (Adjacency Matrix)

用一個二維陣列 matrix 表示頂點之間的連接關係：matrix[i][j] = 1 代表頂點 $i$ 與頂點 $j$ 之間有邊，0 代表沒有邊。

Java 實作

public class AdjacencyMatrix {
    public static void main(String[] args) {
        int n = 5; // 5 個頂點 (0 ~ 4)
        int[][] matrix = new int[n][n];

        addEdge(matrix, 0, 1);
        addEdge(matrix, 0, 3);
        addEdge(matrix, 1, 2);
        addEdge(matrix, 2, 4);
        addEdge(matrix, 3, 4);

        System.out.println("Adjacency Matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    static void addEdge(int[][] matrix, int u, int v) {
        matrix[u][v] = 1;
        matrix[v][u] = 1; // 無向圖，兩個方向都設定
    }
}

鄰接串列 (Adjacency List)

每個頂點對應一個串列，存放所有相鄰頂點。實務中更常見——大多數圖的邊數遠少於頂點數的平方，鄰接串列可節省大量記憶體。

Java 實作

import java.util.*;

public class AdjacencyList {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i = 0; i <= 4; i++) graph.putIfAbsent(i, new ArrayList<>());

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 3);
        addEdge(graph, 1, 2);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);

        System.out.println("Adjacency List:");
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            System.out.println("Vertex " + entry.getKey() + " -> " + entry.getValue());
        }
    }

    static void addEdge(Map<Integer, List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u); // 無向圖
    }
}

以下互動圖解把「鄰接矩陣」與「鄰接串列」放在同一張圖旁邊對照——滑鼠移到任一頂點，會同時在兩種表示法中高亮它的相鄰關係：

兩種方式的比較

	鄰接矩陣	鄰接串列
空間複雜度	$O(	V
查詢兩點是否相鄰	$O(1)$	$O(\text{degree})$
走訪所有相鄰頂點	$O(	V
適合使用時機	邊很多（稠密圖）	邊較少（稀疏圖）

（ $\text{degree}$ 是該頂點的度數——它連出的邊數。）

圖的走訪 (Traversal)

與樹相同，分為 DFS 與 BFS 兩種。差別在於圖可能存在環，需額外記錄已拜訪的節點以避免無限迴圈。

以下互動圖解以同一張 5 頂點的圖示範，點按鈕切換 DFS / BFS，動畫會逐一標記節點被拜訪的順序：

以下兩節以這張 5 個頂點的圖為例，邊為 (0,1)、(0,3)、(1,2)、(2,4)、(3,4)，從頂點 0 出發。鄰接串列：

0 → [1, 3]
1 → [0, 2]
2 → [1, 4]
3 → [0, 4]
4 → [2, 3]

深度優先搜尋 (DFS)

思路：一條路走到底，走不通再回頭。通常用遞迴實作。

手把手：從 0 出發

步驟	當前節點	動作	visited	呼叫堆疊
1	0	進入、印 0，先看鄰居 1	{0}	[0]
2	1	進入、印 1，先看鄰居 2（0 已訪）	{0, 1}	[0, 1]
3	2	進入、印 2，先看鄰居 4（1 已訪）	{0, 1, 2}	[0, 1, 2]
4	4	進入、印 4，鄰居 2、3；2 已訪，進 3	{0, 1, 2, 4}	[0, 1, 2, 4]
5	3	進入、印 3，鄰居 0、4 都已訪，回溯	{0, 1, 2, 4, 3}	[0, 1, 2, 4, 3]
6	逐層回溯結束	—	—	空

走訪順序：0 → 1 → 2 → 4 → 3

Java 實作（DFS）

import java.util.*;

public class GraphDFS {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i = 0; i <= 4; i++) graph.putIfAbsent(i, new ArrayList<>());

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 3);
        addEdge(graph, 1, 2);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);

        System.out.print("DFS from vertex 0: ");
        dfs(graph, 0, new HashSet<>());
        System.out.println();
    }

    static void addEdge(Map<Integer, List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static void dfs(Map<Integer, List<Integer>> graph, int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");

        for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited);
            }
        }
    }
}

廣度優先搜尋 (BFS)

思路：先探索所有鄰居，再往更遠處走。使用佇列 (Queue) 實作，確保先發現的鄰居先被處理。

手把手：從 0 出發

步驟	彈出	印	新入列	佇列狀態	visited
0	—	—	0	[0]	{0}
1	0	0	1, 3	[1, 3]	{0, 1, 3}
2	1	1	2（0 已訪）	[3, 2]	{0, 1, 3, 2}
3	3	3	4（0 已訪）	[2, 4]	{0, 1, 3, 2, 4}
4	2	2	無（1、4 都已訪）	[4]	同上
5	4	4	無（2、3 都已訪）	[]	同上

走訪順序：0 → 1 → 3 → 2 → 4（與 DFS 不同——BFS 先把距離 1 的點全訪完，再進到距離 2）

Java 實作（BFS）

import java.util.*;

public class GraphBFS {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i = 0; i <= 4; i++) graph.putIfAbsent(i, new ArrayList<>());

        addEdge(graph, 0, 1);
        addEdge(graph, 0, 3);
        addEdge(graph, 1, 2);
        addEdge(graph, 2, 4);
        addEdge(graph, 3, 4);

        System.out.print("BFS from vertex 0: ");
        bfs(graph, 0);
        System.out.println();
    }

    static void addEdge(Map<Integer, List<Integer>> graph, int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(start);
        queue.offer(start);

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

            for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
}

走訪的時間複雜度

兩種走訪方式在鄰接串列表示下，時間複雜度相同：

	時間複雜度	空間複雜度
DFS	$O(	V
BFS	$O(	V

每個頂點和每條邊各被拜訪一次，所以是 $O(|V| + |E|)$ ，其中 $|V|$ 是頂點數， $|E|$ 是邊數。

DFS 與 BFS 不只是走訪方式，也是解決許多圖相關問題的核心工具：

BFS 天然保證「最少步數」，適合求最短路徑（無權重時）。
DFS 適合偵測環、找連通分量、解決迷宮等需要深入探索的問題。

常見考法

#	題型	重點
1	給邊列畫出鄰接矩陣 / 鄰接串列	無向要雙向、有向單向
2	從某點 DFS / BFS 手跑走訪順序	鄰接串列順序影響結果；DFS 用 stack / 遞迴、BFS 用 queue
3	DFS / BFS 的時間複雜度推導	鄰接串列 $O(V+E)$ 、鄰接矩陣 $O(V^2)$
4	判斷圖是否連通	從任一點 DFS / BFS，訪到的節點 = $V$ → 連通
5	偵測環	無向：DFS 遇到非 parent 的 visited 節點 → 有環；有向：DFS 遇到「灰色」節點 → 有環
6	連通分量數	對未訪節點起 DFS / BFS，跑幾次 = 分量數
7	拓樸排序（DAG）	DFS post-order 反轉；或 Kahn’s（每次取 in-degree = 0）
8	無權最短路徑用 BFS	BFS 層序恰為距離（邊權 = 1）
9	鄰接矩陣 vs 鄰接串列空間比較	稠密圖用矩陣 $O(V^2)$ ；稀疏圖用串列 $O(V+E)$
10	$\sum \deg(v) = 2\\|E\\|$ （握手定理）	無向圖每條邊貢獻 2；有向圖 $\sum \text{in-deg} = \sum \text{out-deg} = \\|E\\|$

複雜度推導

DFS / BFS $O(V + E)$ （鄰接串列）：

\text{每頂點入 visited 一次} \cdot O(1) + \sum_{v \in V} \deg(v) \cdot O(1) = O(V) + O(2E) = O(V + E)

DFS / BFS $O(V^2)$ （鄰接矩陣）：每個頂點要掃整列 $V$ 格才能找鄰居：

\sum_{v \in V} O(V) = O(V^2)

拓樸排序 Kahn’s $O(V + E)$ ：建 in-degree 掃 $E$ ；每頂點入/出 queue 一次 $O(V)$ ；處理每條邊 $O(E)$ 。

考試常踩的陷阱

DFS / BFS 結果不唯一：取決於鄰居處理順序（鄰接串列的順序）
無向圖偵測環要排除 parent：否則每條邊都會被當成「回邊」
有向圖偵測環用三色：白（未訪）、灰（訪中）、黑（訪完）；回到灰才是環
BFS 最短路徑只對無權圖：有權要 Dijkstra / Bellman-Ford
拓樸排序只適用 DAG：有環就沒有合法拓樸序
鄰接矩陣對無向圖是對稱矩陣： $M[i][j] = M[j][i]$
度數 vs 入/出度：無向只有 deg；有向要分 in-degree、out-degree

實際應用

場景	用到的概念
Google Maps 路徑規劃	有權圖 + 最短路徑演算法（如 Dijkstra）
社群媒體好友推薦	無向圖 + BFS（找朋友的朋友）
網頁排名 (PageRank)	有向圖 + 連通性分析
任務排程 / 相依分析	有向無環圖 (DAG) + 拓樸排序
電腦網路連線偵測	無向圖 + 連通性偵測