圖是模型化關係網絡的核心資料結構，支援連通性判斷、最短路徑、最小生成樹等演算法。選擇適當的表示法直接決定時空效率。本文系統比較三大主流表示法，附 C 語言結構定義與適用場景分析。
用二維陣列 graph[V][V] 存儲邊關係，graph[u][v] = 1/權重 表示邊存在。
// 無向無權圖
int graph[5][5] = {
{0,1,0,1,1},
{1,0,1,0,1},
{0,1,0,1,0},
{1,0,1,0,1},
{1,1,0,1,0}
};
// 有向帶權圖
int graph[5][5] = {
{0,0,0,0,0},
{3,0,0,0,0},
{0,6,0,0,0},
{8,0,4,0,0},
{9,2,0,7,0}
};
| 操作 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 判斷邊存在 | O(1) | O(V²) | 最快查詢 |
| 插入/刪除邊 | O(1) | ||
| 遍歷鄰接點 | O(V) | 掃描整行 | |
| 適用場景 | 稠密圖（E ≈ V²）、頻繁邊查詢、Floyd-Warshall | ||
將所有邊平鋪存儲，每條邊記錄起點、終點、權重、是否有向。
typedef struct Edge {
int from, to;
int weight;
int directed; // 0=無向, 1=有向
} Edge;
Edge edges[MAX_E];
int edge_count = 0;
| 操作 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 判斷邊存在 | O(E) | O(E) | 需線性掃描 |
| 插入邊 | O(1) | 陣列尾部追加 | |
| Kruskal 演算法 | O(E log E) | 天然適合（需排序邊） | |
| 適用場景 | 邊為中心演算法、稀疏圖、需排序邊權重 | ||
每個頂點維護一條鏈表/向量，存儲其出邊。兼顧空間效率與遍歷速度。
typedef struct ArcNode {
int dest; // 終點
int weight;
struct ArcNode *next; // 同起點的下一條邊
} ArcNode;
typedef struct VertexNode {
int id;
int in_degree, out_degree;
ArcNode *first_arc; // 第一條出邊
} VertexNode;
typedef struct Graph {
int vex_num, arc_num;
VertexNode vertices[MAX_V];
} Graph;
| 操作 | 時間 | 空間 | 備註 |
|---|---|---|---|
| 判斷邊存在 | O(deg(u)) | O(V+E) | 遍歷鏈表 |
| 遍歷鄰接點 | O(deg(u)) | 最優 | |
| BFS/DFS/Dijkstra | O(V+E) | 標準複雜度 | |
| 適用場景 | 稀疏圖（E ≪ V²）、大多數圖演算法、工程通用 | ||
靜態圖的極致優化，三個陣列：
offset[V+1]：每個頂點鄰接表在 neighbors 中的起始索引neighbors[E]：緊湊存儲所有鄰接點weights[E]：對應權重（可選）優勢：緊湊記憶體佈局、CPU 緩存友好、適合 GPU 平行遍歷。劣勢：動態插刪困難。
vector<vector<pair<int,int>>> 或 Boost.Graph沒有完美的圖表示，只有適合場景的表示。理解三大表示法的時空權衡、掌握鄰接表的指標操作與 CSR 的陣列映射，是演算法工程師處理網絡流、社交圖譜、路由規劃等問題的基本功。
