圖的表示法與廣度優先搜尋 (Graph Representations and BFS)

重點總覽 (Overview)

圖與相鄰矩陣 (Graph & Adjacency Matrix)

• Vertex(頂點):實體,給定唯一 vertex id。
• Edge(邊):關係。本章用 directional(有箭頭,source → destination)。
• Adjacency matrix:若有邊 i→j 則 A[i][j]=1,否則 0(留白)。

本章範例(Fig. 15.1):9 vertices、15 directional edges。

        dst →  0  1  2  3  4  5  6  7  8     row sum (out-degree)
 src ↓
   0           .  1  1  .  .  .  .  .  .        2     0→1, 0→2
   1           .  .  .  1  1  .  .  .  .        2     1→3, 1→4
   2           .  .  .  .  .  1  1  1  .        3     2→5, 2→6, 2→7
   3           .  .  .  .  1  .  .  .  1        2     3→4, 3→8
   4           .  .  .  .  .  1  .  .  1        2     4→5, 4→8
   5           .  .  .  .  .  .  1  .  .        1     5→6
   6           .  .  .  .  .  .  .  .  1        1     6→8
   7           1  .  .  .  .  .  1  .  .        2     7→0, 7→6
   8           .  .  .  .  .  .  .  .  .        0

稀疏 vs. 全連接 (Sparse vs. Fully Connected)

稀疏儲存格式 CSR / CSC / COO (Sparse Storage Formats)

命名約定(本章專用):列索引/指標稱 src / srcPtrs;行索引/指標稱 dst / dstPtrs。因為矩陣的「列 = source vertex、行 = destination vertex」。

CSR (Compressed Sparse Row) — 按 source 分組

srcPtrs[v] = vertex v 的 outgoing edges 起始位置 → 快速取得出邊。

srcPtrs : [ 0  2  4  7  9 11 12 13 15 15 ]   (長度 N+1 = 10)
            v0 v1 v2 v3 v4 v5 v6 v7 v8 end
dst     : [ 1  2 | 3  4 | 5  6  7 | 4  8 | 5  8 | 6 | 8 | 0  6 ]   (長度 E = 15)
 index    0  1   2  3    4  5  6   7  8   9 10  11  12  13 14

• 讀法:srcPtrs[3]=7、srcPtrs[4]=9 → vertex 3 的出邊在 dst[7..8] = {4, 8},即邊 3→4、3→8。

CSC (Compressed Sparse Column) — 按 destination 分組

dstPtrs[v] = vertex v 的 incoming edges 起始位置 → 快速取得入邊(predecessors)。

dstPtrs : [ 0  1  2  3  4  6  8 11 12 15 ]
src     : [ 7 | 0 | 0 | 1 | 1  3 | 2  4 | 2  5  7 | 2 | 3  4  6 ]
            ↑v0  ↑v1 ↑v2 ↑v3  ↑v4    ↑v5     ↑v6   ↑v7   ↑v8

• 讀法:vertex 8 的入邊 = src[12..14] = {3, 4, 6},即 3→8, 4→8, 6→8。

COO (Coordinate) — 每邊一筆 (src, dst)

src : [ 0 0 1 1 2 2 2 3 3 4 4 5 6 7 7 ]
dst : [ 1 2 3 4 5 6 7 4 8 5 8 6 8 0 6 ]   ← 第 k 筆 = 邊 src[k]→dst[k]

格式對照 (Format Comparison)

公式(CSR 省儲存比):

adjacency matrix 儲存 = N²                    = 81
CSR 儲存(無 data)    = (N+1) + E             = 25
real-world(極稀疏) → 節省可達數個數量級

廣度優先搜尋 (Breadth-First Search, BFS)

• 目的:找從一點到另一點需走的最少邊數(shortest hop count)。
• summary 方式:給一個 root,把每個 vertex label 成「從 root 走到它的最小邊數 = level / depth」。
• vertex degree distribution 會影響演算法選擇:道路網 degree 均勻且低;Twitter follower 圖 degree 分布廣(名人 = 高 degree)。

Level labeling = wavefront(以 root = 0)

Level 0 :  0                         (root)
Level 1 :  1   2                     經 1 條邊:0→1, 0→2
Level 2 :  3   4   5   6   7         3,4 ← via 1 ; 5,6,7 ← via 2
Level 3 :  8                         8 ← via 3 或 4 或 6

root 換成 2,結果差很多(雖只差 1 條邊):L1={5,6,7}、L2={8(via 6), 0(via 7)}、L3={1(via 0)}、L4={3,4(via 1)}。root 不同 → BFS 結果截然不同。

BFS tree 與最短路徑回溯 (BFS Tree & Path Backtrace)

• BFS tree:所有被 label 的 vertices + 只保留「level L → level L+1」實際走過的邊。
• vertex 的 level = root 到它的最短邊數(例:root=2 時 vertex 1 = level 3 → 最短 3 條邊)。
• 回溯路徑:從目標往回走,每步挑「level 比目前小 1」的 predecessor;若有多個,任挑一個都正確(代表存在多條等長最短路徑)。

sequential BFS level-labeling (概念,平行版見 sibling notes)
level[root] = 0; 其餘 = INF
for L = 0, 1, 2, ...:
    for each v with level[v] == L:
        for each neighbor u of v (via outgoing edge):
            if level[u] == INF:   level[u] = L + 1
    若本輪無新 label → 結束

path backtrace (需 incoming edges / CSC):
cur = target
while cur != root:
    pick predecessor p of cur with level[p] == level[cur] - 1
    output edge p→cur ; cur = p

• 範例:root=2 找到 vertex 1 → 從 1 選 0、再選 7、再選 2 → 路徑 2-7-0-1。
• 從 0 到 5 的三條路:0-1-3-4-5、0-1-4-5、0-2-5(後者最短)。

複雜度:

BFS 走訪每個 vertex 一次、每條 edge 一次 → O(V + E)

應用:Maze Routing(IC 繞線)

• 從 root net terminal 做 BFS:每個非 blockage 的上下左右鄰居標 level 1,再外擴 level 2、3…形成 wavefront。
• 本例(Fig. 15.5):level 1 = 4 個、level 2 = 8 個、level 3 = 12 個 → wavefront 一開始小,但數層後迅速暴增(對平行化既是機會也是 load balance 挑戰)。

maze wavefront from root R (上下左右擴張)
              · 3 ·            level 1 : 4  個 (R 的四鄰)
            3 2 1 2 3          level 2 : 8  個
            · 1 R 1 ·          level 3 : 12 個
            3 2 1 2 3          ...      逐層 +4 (空曠時)
              · 3 ·

• BFS 完成後,從 target 回溯 predecessor(level −1)即得一條最短繞線;多 predecessor → 多條等長路,可用 heuristic 挑「對後續繞線最不卡」的那條。

考試/面試重點 (Exam / Test Patterns)

Related Notes

• 15-Graph-Traversal/02-Vertex-Centric-and-Edge-Centric-BFS
• 15-Graph-Traversal/03-Frontiers-Privatization-and-Optimizations
• 14-Sparse-Matrix-Computation/01-Sparse-Matrices-and-Basic-Formats-COO-CSR
• 14-Sparse-Matrix-Computation/02-Regularized-Formats-ELL-Hybrid-JDS
• 03-Multidimensional-Grids-And-Data/02-Mapping-Threads-to-Multidimensional-Data