目錄

一、圖的定義

1.1 圖的基本概念

1.2 圖的分類

（1）按邊的方向：

（2）按邊的權值：

（3）按邊的數量和類型：

（4）按連通性：

1.3 圖的基本術語

二、圖的表示方法

2.1 鄰接矩陣（Adjacency Matrix）

2.2 鄰接表（Adjacency List）

2.3 邊列表（Edge List）

2.4 關聯矩陣（Incidence Matrix）

三、圖的關系建模

3.1 建模基本思路

3.2 表結構設計

（1）頂點表設計

（2）邊表設計（適用于有向圖）

（3）標簽元數據表設計

（4）無向圖處理方法

附

1 圖的基本結構相關概念

2圖的類型和性質

3 圖的遍歷與算法相關概念

4 圖的矩陣表示與運算

5 高階圖模型與擴展概念

---

圖論（Graph Theory）是計算機科學中研究“對象之間關系”的重要分支，它以“圖”作為基本結構來建模現實世界中各種“點”和“連接”。本篇文章將系統介紹圖的基礎概念——圖的定義與圖的表示方法，幫助讀者構建圖論學習的核心框架。

一、圖的定義

1.1 圖的基本概念

一個圖（Graph）是由一組頂點（Vertices）和一組邊（Edges）構成的集合結構。用數學符號表示為：

G = (V, E)

其中：

• V 是圖中頂點的集合，通常記作 V = \{v_1, v_2, \ldots, v_n\}；

• E 是圖中邊的集合，每條邊連接兩個頂點。

邊可以是無向的，也可以是有向的。

1.2 圖的分類

圖根據其結構特性可以細分為多種類型：

（1）按邊的方向：

• 無向圖（Undirected Graph）：邊不具備方向性，(u, v) 與 (v, u) 等價；

• 有向圖（Directed Graph）：邊具有方向性，(u, v) 表示從 u 指向 v。

（2）按邊的權值：

• 非加權圖（Unweighted Graph）：所有邊等價；

• 加權圖（Weighted Graph）：每條邊都有一個權值（如距離、代價等），表示邊的“強度”或“成本”。

（3）按邊的數量和類型：

• 簡單圖（Simple Graph）：不含重邊和自環；

• 多重圖（Multigraph）：允許兩個頂點之間存在多條邊（重邊）；

• 偽圖（Pseudograph）：允許自環和重邊。

（4）按連通性：

• 連通圖（Connected Graph）：無向圖中任意兩個頂點之間至少存在一條路徑；

• 強連通圖（Strongly Connected Graph）：有向圖中任意兩點之間都可互達；

• 弱連通圖（Weakly Connected Graph）：有向圖在忽略方向后是連通的。

1.3 圖的基本術語

• 頂點（Vertex）：圖中的基本單位；

• 邊（Edge）：連接兩個頂點的線段，表示關系；

• 度（Degree）：

  • 無向圖中：一個頂點的度是連接該頂點的邊數；

  • 有向圖中：包括入度（In-degree）*和*出度（Out-degree）；

• 路徑（Path）：由一系列連續邊組成的頂點序列；

• 簡單路徑（Simple Path）：路徑中頂點不重復；

• 環（Cycle）：起點和終點相同的簡單路徑；

• 自環（Loop）：起點和終點為同一頂點的邊；

• 重邊（Multiple Edge）：連接同一對頂點的多條邊；

• 稀疏圖與稠密圖：

  • 稀疏圖：邊的數量遠小于頂點對的數量；

  • 稠密圖：邊的數量接近最大邊數（例如 n(n-1)/2）。

二、圖的表示方法

在計算機中使用圖時，必須選擇合適的數據結構對其進行編碼。常見的圖表示方式包括：

2.1 鄰接矩陣（Adjacency Matrix）

鄰接矩陣是一種二維數組 A[n][n]，用來表示頂點之間是否相連。

• 若 i 與 j 之間有邊，則 A[i][j] = 1（或等于權重）；

• 否則 A[i][j] = 0；

• 無向圖的鄰接矩陣是對稱的；

• 有向圖不一定對稱。

示例：

設圖 G 有 3 個頂點，邊為 (0, 1), (1, 2)，鄰接矩陣為：

  0 1 2
0 0 1 0
1 1 0 1
2 0 1 0

優點：

• 查詢任意兩點是否連接只需 O(1) 時間；

• 結構簡單，適用于稠密圖。

缺點：

• 空間復雜度為 O(n^2)，不適用于稀疏圖。

2.2 鄰接表（Adjacency List）

鄰接表用一個數組加多個鏈表來表示圖：

• 每個頂點擁有一個鏈表，鏈表中記錄與該頂點相鄰的頂點；

• 對于無向圖，每條邊需在兩個頂點的鏈表中都出現；

• 對于有向圖，只記錄出邊。

示例：

0: 1 ?
1: 0 → 2 ?
2: 1

優點：

• 空間復雜度為 O(n + m)，適合稀疏圖；

• 遍歷某一頂點的鄰接點效率高。

缺點：

• 查詢兩點之間是否有邊需遍歷鏈表，最壞為 O(n)。

---

2.3 邊列表（Edge List）

邊列表使用一個列表來記錄圖中所有邊：

• 每條邊表示為一個二元組 (u, v) 或三元組 (u, v, w)（帶權）；

• 通常用于圖算法中。

示例：

[(0, 1), (1, 2)]

優點：

• 簡單直接，節省空間；

• 適合用于邊排序、生成樹等算法。

缺點：

• 查詢效率低，不利于鄰接點快速訪問。

---

2.4 關聯矩陣（Incidence Matrix）

關聯矩陣是一個 n \times m 的矩陣（n 是頂點數，m 是邊數）：

• 無向圖中，若邊 e_j 與頂點 v_i 相連，則 M[i][j] = 1；

• 有向圖中，若 v_i 是起點則 M[i][j] = 1，若 v_i 是終點則 M[i][j] = -1。

優點：

• 可用于代數圖理論分析；

• 明確表示頂點與邊的連接關系。

缺點：

• 在實際編程中使用不多，空間浪費較大。

表示方法對比:

表示方法	空間復雜度	查詢邊是否存在	枚舉鄰接點	適用場景
鄰接矩陣	O(n^2)	O(1)	O(n)	稠密圖
鄰接表	O(n + m)	最壞 O(n)	O(k)	稀疏圖
邊列表	O(m)	O(m)	不適用	構建/排序
關聯矩陣	O(n \times m)	O(m)	不適用	理論研究

三、圖的關系建模

雖然圖結構在本質上是非關系型的，但在沒有圖數據庫（如 Neo4j、JanusGraph）可用的場景下，我們仍可以通過關系型數據庫（RDBMS）來表達圖的數據結構與連接關系。

3.1 建模基本思路

圖在 RDBMS 中建模的核心思想是將頂點和邊分別表示為關系表（Relation）：

• 頂點表（Vertex Table）：存儲圖中的所有節點；

• 邊表（Edge Table）：存儲圖中所有的邊（連接關系）。

3.2 表結構設計

（1）頂點表設計

CREATE TABLE vertex (id INT PRIMARY KEY, ? ? ? ? -- 頂點唯一標識label_id INT NOT NULL, ? ? ?-- 頂點類型properties JSON, ? ? ? ? ? ?-- 頂點屬性FOREIGN KEY (label_id) REFERENCES label(id)
);

properties 字段可以靈活地以 JSON 形式存儲各類屬性，適合屬性異構的圖場景。如果屬性固定，也可將其展開為單獨的列。

（2）邊表設計（適用于有向圖）

CREATE TABLE edge (id INT PRIMARY KEY, ? ? ? ? ? ? ?-- 邊的唯一標識from_vertex INT NOT NULL, ? ? ? ?-- 起點to_vertex INT NOT NULL, ? ? ? ? ?-- 終點label_id INT NOT NULL, ? ? ? ? ? -- 邊的類型weight DECIMAL(10,2), ? ? ? ? ? ?-- 權重properties JSON, ? ? ? ? ? ? ? ? -- 邊的屬性FOREIGN KEY (from_vertex) REFERENCES vertex(id),FOREIGN KEY (to_vertex) REFERENCES vertex(id),FOREIGN KEY (label_id) REFERENCES label(id)
);

• 該結構適用于有向圖（Directed Graph）；

• 支持為每條邊添加類型、權重或其他靈活的屬性；

• 使用外鍵約束維護邊和頂點之間的完整性。

（3）標簽元數據表設計

CREATE TABLE label (id INT PRIMARY KEY, ? ? ? ? ? ?-- 標簽唯一標識label VARCHAR(100), ? ? ? ? ? ?-- 標簽名稱category INT NOT NULL ? ? ? ? ?-- 標簽分類：標識頂點標簽還是邊標簽（例如：1=頂點，2=邊）
);

（4）無向圖處理方法

對于無向圖（Undirected Graph），可使用以下兩種策略之一：

1. 對稱存儲：每條邊存儲兩次，分別是 (u → v) 和 (v → u)；

2. 約束存儲順序：強制存儲一次，并約定 from_vertex < to_vertex，查詢時統一處理對稱性。

---

附

1 圖的基本結構相關概念

概念	簡要說明
頂點（Vertex）	圖中的節點，代表事物
邊（Edge）	頂點之間的連接，代表關系
度（Degree）	頂點的連接數目（有向圖分入度、出度）
權值（weight cost）	頂點或邊的附加屬性
自環（Loop）	一條連接自身的邊，如 (v, v)
重邊（Multiple Edge）	多條連接同一對頂點的邊
鄰接（Adjacency）	兩頂點之間有邊連接稱為鄰接
路徑（Path）	一組連接頂點的邊序列
簡單路徑	路徑中無重復頂點
環（Cycle）	起點和終點相同的簡單路徑
簡單圖（Simple Graph）	無自環、無重邊的圖
多重圖（Multigraph）	允許重邊和/或自環
子圖（Subgraph）	圖的頂點和邊的子集組成的圖
完全圖（Complete Graph）	任意兩頂點之間都存在一條邊
稀疏圖/稠密圖	邊的數量相對少/多
平面圖（Planar Graph）	可以畫在平面上不相交的圖
偽圖（Pseudograph）	允許重邊和自環的圖

2圖的類型和性質

概念	簡要說明
有向圖（Directed Graph）	邊有方向，表示從 u → v
無向圖（Undirected Graph）	邊無方向，(u, v) 與 (v, u) 等價
加權圖（Weighted Graph）	邊帶有權值，代表代價、距離等
非加權圖	邊權相同或無權
連通圖（Connected Graph）	任意兩頂點之間都有路徑（無向圖）
強連通圖（Strongly Connected）	有向圖中任意兩頂點可達
弱連通圖	有向圖忽略方向后連通
二分圖（Bipartite Graph）	頂點集可分為兩部分，邊僅連接不同集合
森林（Forest）	不含環的無向圖
樹（Tree）	連通的無環無向圖
DAG（有向無環圖）	沒有有向環的有向圖（常用于任務調度）
歐拉圖（Eulerian Graph）	存在一條路徑遍歷每條邊恰好一次
哈密頓圖（Hamiltonian Graph）	存在一條路徑遍歷每個頂點恰好一次

3 圖的遍歷與算法相關概念

概念	簡要說明
深度優先遍歷（DFS）	類似樹的先序遍歷
廣度優先遍歷（BFS）	層次搜索方式
拓撲排序（Topological Sort）	DAG 的頂點線性排序
連通分量（Connected Component）	最大的連通子圖
割點（Articulation Point）	刪除該點會使圖不連通
橋（Bridge）	刪除這條邊會使圖不連通
圖染色（Graph Coloring）	給圖的頂點上色，使相鄰點顏色不同
最小生成樹（Minimum Spanning Tree）	覆蓋所有頂點、權值最小的樹
最短路徑（Shortest Path）	頂點之間路徑權值最小
網絡流（Network Flow）	求最大流/最小割等問題
匹配（Matching）	二分圖中點之間的配對關系
圖同構（Graph Isomorphism）	判斷兩個圖是否結構一致
圖壓縮（Graph Compression）	將多個頂點合并成一個頂點

4 圖的矩陣表示與運算

概念	簡要說明
鄰接矩陣（Adjacency Matrix）	頂點對之間的連接關系
鄰接表（Adjacency List）	每個頂點的鄰接頂點列表
關聯矩陣（Incidence Matrix）	頂點和邊的對應關系
距離矩陣（Distance Matrix）	所有頂點對之間的最短路徑長度
拉普拉斯矩陣（Laplacian Matrix）	用于譜圖理論分析
權重矩陣（Weight Matrix）	記錄邊權重
冪矩陣（A^k）	表示頂點之間的 k 步路徑數量

5 高階圖模型與擴展概念

概念	簡要說明
超圖（Hypergraph）	一條邊可以連接多個頂點
動態圖（Dynamic Graph）	圖結構隨時間變化
隨機場（Random Graph）	邊的生成遵循概率模型（如 Erd?s–Rényi）
社區結構（Community）	圖中頂點聚類成的子結構
小世界圖（Small-world）	局部聚集 + 全局稀疏的圖模型
無標度圖（Scale-free）	頂點度數滿足冪律分布