圖論2 圖的數據結構表示

一圖的數據結構表示

1 鄰接矩陣（Adjacency Matrix）

2 鄰接表（Adjacency List）

3 邊列表（Edge List）

4 十字鏈表（Orthogonal List / Cross-linked List, 十字鏈表）

5 鄰接多重表（Adjacency Multilist / Incidence List for Undirected Graphs）

6 關聯矩陣（Incidence Matrix / 關聯矩陣）

二圖的 RDBMS 建模

1 建模基本思路

2 表結構設計

（1）頂點表設計

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

（3）標簽元數據表設計

（4）無向圖處理方法

三圖算法基礎數據結構-鄰接表

1 鄰接表建模思路

2 代碼實現

(1) 標簽類 Label

(2) 頂點類 Vertex

(3) 邊類 Edge

(4) 圖類 AdjacencyGraph

3 說明

在上文已經介紹圖的基本概念之后，本節將圍繞圖的數據結構表示展開，系統介紹常見的在內存中表示圖的幾種經典數據結構：鄰接矩陣、鄰接表、邊列表、十字鏈表、鄰接多重表、關聯矩陣，并給出每種表示的定義、存儲結構、優缺點、適用場景、復雜度分析與Java樸素實現。最后討論如何在關系型數據庫（RDBMS）中建模圖結構。

一圖的數據結構表示

1 鄰接矩陣（Adjacency Matrix）

定義與結構 鄰接矩陣用于表示頂點集合為 V=\{v_0,\dots,v_{n-1}\} 的圖。構造一個 n\times n 的二維矩陣 A，對于無向圖，A[i][j]=1 表示頂點 v_i 與 v_j 之間存在邊；若有權圖則放權值 A[i][j]=w；無邊時可用 0、∞ 或 null 表示，取決于實現。

舉例（無向無權）頂點 0 與 2 有邊，則 A[0][2] = A[2][0] = 1。

優點

隨機訪問邊存在性：判斷兩頂點是否相鄰為 O(1)。
矩陣代數便于做圖論中的一些理論運算。
實現簡單，適合頂點數 n 較小或圖密集（邊數接近 n^2）時使用。

缺點

空間復雜度為 O(n^2)，對稀疏圖非常浪費。
枚舉某一頂點的鄰居需要 O(n) 掃描整行（即使度很小也要掃描）。
動態插入大量頂點成本高（需要擴展矩陣）。

復雜度

空間：O(n^2)
判斷邊存在：O(1)
枚舉鄰居：O(n)
插入/刪除邊：O(1)

適用場景

n 小或圖密集（dense graph）。
需要頻繁 O(1) 邊查找或矩陣運算（例如某些線性代數方法）。

Java樸素實現

/*** 圖的鄰接矩陣表示*/
public class MatrixGraph<V,E,ED> {
?// 最大頂點個數public static final int MAX_VERTEX_NUM = 20;// 頂點向量集合,用來存儲頂點信息,數組索引作為數據索引,用來構建鄰接矩陣private Vertex<V>[] vexs;// 鄰接矩陣private AdjMatrix<E,ED> arcs = new AdjMatrix<>();// 圖的當前頂點數和弧數public int vexnum;public int arcnum;// 圖的種類標志public GraphKind kind;
?@SuppressWarnings("unchecked")public MatrixGraph() {vexs = (Vertex<V>[])new Vertex<?>[MAX_VERTEX_NUM];// 初始化鄰接矩陣的每個單元格for (int i = 0; i < MAX_VERTEX_NUM; i++) {for (int j = 0; j < MAX_VERTEX_NUM; j++) {arcs.cells[i][j] = new ArcCell<>();}}}
?// 圖的種類 {有向圖,有向網,無向圖,無向網}public enum GraphKind { DG, DN, UDG, UDN }
?public static class Vertex<V>{public V data;}
?// 弧單元定義public static class ArcCell<E,ED> {// 頂點關系類型。對無權圖,用 1 或 0 表示相鄰否;對帶權圖,則為權值類型public E adj;
?// 該弧相關信息public ED info;}
?// 鄰接矩陣類型public static class AdjMatrix<E,ED> {public ArcCell<E,ED>[][] cells = new ArcCell[MAX_VERTEX_NUM][MAX_VERTEX_NUM];}
?// 提供訪問vexs和arcs的公共方法public Vertex<V>[] getVexs() {return vexs;}
?public AdjMatrix<E,ED> getArcs() {return arcs;}
?
}

2 鄰接表（Adjacency List）

定義與結構 鄰接表為每個頂點維護一個鄰居列表（通常鏈表、動態數組或向量），每個列表包含該頂點的所有出/入（或無向）鄰接頂點及可選的邊權和邊屬性。

舉例（有向有權） adj[u] 列表中存儲 (v, weight, metadata) 表示從 u 到 v 的邊。

優點

空間友好：空間復雜度為 O(n + m)，其中 m 是邊數，適用于稀疏圖。
枚舉某一頂點的所有出邊非常高效，時間與該頂點度數成正比。
插入邊易，刪除邊在雙向鏈表或帶索引結構中也較為方便。

缺點

判斷任意兩頂點是否有邊不是 O(1)（需要掃描較短列表或使用輔助哈希）。
若需要高并發、并行訪問單個頂點的鄰居，需考慮同步和鎖策略。

復雜度

空間：O(n + m)
枚舉某一頂點鄰居：O(\deg(v))
判斷邊存在（線性掃描）：O(\deg(u))
插入邊：均攤 O(1)
刪除邊：O(\deg(u))（可借輔助索引優化）

適用場景

大多數實際稀疏圖（社交網絡、道路網絡、依賴圖等）。
常配合圖遍歷（BFS、DFS）、最短路徑算法（Dijkstra、Bellman-Ford）使用。

Java樸素實現

/*** 圖的鄰接表數據結構表示*/
public class AdjacencyListGraph<V, E> {public static final int MAX_VERTEX_NUM = 20;public VNode<V, E>[] vertices; ? ? ? ? // 鄰接表public int vexnum; ? ? ? ? ? ? ? ? ? ? // 圖的當前頂點數public int arcnum; ? ? ? ? ? ? ? ? ? ? // 圖的當前弧數public GraphKind kind = GraphKind.UDG; // 圖的種類標志
?@SuppressWarnings("unchecked")public AdjacencyListGraph() {vertices = (VNode<V, E>[]) new VNode<?,?>[MAX_VERTEX_NUM];vexnum = 0;arcnum = 0;}
?// 圖的種類 {有向圖,有向網,無向圖,無向網}public enum GraphKind { DG, DN, UDG, UDN }
?// 弧節點類public static class ArcNode<E> {public int adjvex; ? ? ? ? ?  // 該弧所指向的頂點的位置public ArcNode<E> nextarc; ?  // 指向下一條弧的指針public E info; ? ? ? ? ? ? ?  // 該弧相關信息的指針（泛型類型）
?public ArcNode(int adjvex, E info) {this.adjvex = adjvex;this.info = info;this.nextarc = null;}}
?// 頂點節點類public static class VNode<V, E> {public V data; ? ? ? ? ? ? ?  // 頂點信息（泛型類型）public ArcNode<E> firstarc; ? // 指向第一條依附該頂點的弧的指針
?public VNode(V data) {this.data = data;this.firstarc = null;}}
?// 示例使用方法public void addVertex(int index, V data) {if (index >= 0 && index < MAX_VERTEX_NUM) {vertices[index] = new VNode<>(data);vexnum++;}}
?public void addArc(int fromIndex, int toIndex, E info) {if (fromIndex >= 0 && fromIndex < MAX_VERTEX_NUM && toIndex >= 0 && toIndex < MAX_VERTEX_NUM) {ArcNode<E> newArc = new ArcNode<>(toIndex, info);newArc.nextarc = vertices[fromIndex].firstarc;vertices[fromIndex].firstarc = newArc;arcnum++;}}
}

3 邊列表（Edge List）

定義與結構 邊列表把圖表示為一組邊的集合，每條邊表示為二元組（或三元組帶權）：(u, v) 或 (u, v, w)。通常用數組 edges[] 存儲。

優點

表示簡單、緊湊，易于序列化與外部存儲。
適合做基于邊的批處理算法（如 Kruskal 最小生成樹需要排序邊）。
插入邊非常簡單（append）。

缺點

判斷邊是否存在需要 O(m)（除非配合索引或哈希）。
枚舉某一頂點的鄰居低效（需掃描全部邊或建立額外索引）。

復雜度

空間：O(m)
遍歷所有邊：O(m)
判斷邊存在：O(m)（可建哈希加速）
插入邊：O(1)（append）

適用場景

批量邊處理（排序、過濾、圖轉化）。
構建初始圖數據后再轉換為鄰接表進行算法處理。
文件格式與數據交換（如 CSV、邊列表文件）。

Java樸素實現

/*** 圖的邊列表表示*/
public class EdgeListGraph<V,E> {public static final int MAX_EDGE_NUM = 20;public Edge<V,E>[] edges;public int edgenum;
?public EdgeListGraph(){this.edges = (Edge<V,E>[])new Edge<?,?>[MAX_EDGE_NUM];this.edgenum = 0;}
?// 邊類包含頂點數據，不包含頂點對象引用public static class Edge<V,E>{V fromData; ?// 直接存儲頂點數據V toData;E data;public Edge(V fromData, V toData, E data){this.fromData = fromData;this.toData = toData;this.data = data;}}
}

4 十字鏈表（Orthogonal List / Cross-linked List, 十字鏈表）

定義與結構 十字鏈表是面向有向圖的一種鏈式表示，期望同時高效訪問每個頂點的入邊和出邊。結構通常包含頂點節點數組，每個頂點維護兩個鏈首：出邊鏈表和入邊鏈表；每條邊節點包含 hlink 指向相同弧在出鏈中的下一個弧，tlink 指向相同弧在入鏈中的下一個弧，以及 tailvex（弧尾頂點）、headvex（弧頭頂點）和邊權等信息。

示意結構

Vertex {firstout; // 指向以該頂點為尾的第一條弧firstin;  // 指向以該頂點為頭的第一條弧
}
Edge {tailvex, headvex;tlink; // 在尾鏈（出鏈）上hlink; // 在頭鏈（入鏈）上weight, info;
}

優點

同時支持對入邊和出邊的高效遍歷：枚舉出邊或入邊都只需沿對應鏈表遍歷。
適合需要頻繁雙方訪問（入邊和出邊）的有向圖算法（如強連通分量、反向遍歷等）。

缺點

較鄰接表實現更復雜（邊維護兩個鏈指針）。
空間開銷較鄰接表稍大（每條邊額外的指針字段）。
在無向圖上不適用（無向圖可用鄰接多重表替代）。

復雜度

空間：O(n + m)
枚舉出邊/入邊：O(\deg_{out}(v)) 或 O(\deg_{in}(v))
插入邊：O(1)
刪除邊：需要維護兩條鏈，復雜度 O(1) 在已知前驅時，否則需要搜索。

適用場景

有向圖且經常需要訪問入邊與出邊。
圖分析。

Java樸素實現

/*** 有向圖的十字鏈表存儲表示*/
public class OrthogonalListGraph<V, E> {public static final int MAX_VERTEX_NUM = 20;public VexNode<V,E>[] xlist; ? ? ? ?// 表頭向量（頂點數組）public int vexnum; ? ? ? ? ? ? // 有向圖的當前頂點數public int arcnum; ? ? ? ? ? ? // 有向圖的當前弧數
?@SuppressWarnings("unchecked")public OrthogonalListGraph() {xlist = (VexNode<V,E>[]) new VexNode<?,?>[MAX_VERTEX_NUM];vexnum = 0;arcnum = 0;}
?public static class ArcBox<E> {public int tailvex; ? ? ? ?// 該弧的尾頂點的位置public int headvex; ? ? ? ?// 該弧的頭頂點的位置public ArcBox<E> hlink; ? ?// 弧頭相同的弧的鏈域public ArcBox<E> tlink; ? ?// 弧尾相同的弧的鏈域public E info; ? ? ? ? ? ? // 該弧相關信息的指針}
?public static class VexNode<V,E> {public V data; ? ? ? ? ? ? // 頂點數據public ArcBox<E> firstin; ?// 指向該頂點第一條入弧public ArcBox<E> firstout; // 指向該頂點第一條出弧}
}

5 鄰接多重表（Adjacency Multilist / Incidence List for Undirected Graphs）

定義與結構 鄰接多重表主要為無向圖服務，目的是避免在無向圖中對同一條邊做兩次獨立記錄（在普通鄰接表中無向邊常被記錄兩次：u->v 和 v->u）。鄰接多重表為每條無向邊只創建一個邊結點，邊結點有兩個指針分別連接到兩個端點的鄰接鏈表中。

示意結構

Edge {iVex, jVex; ? ? ? // 兩端點iLink, jLink; // 分別連接到 v1 的鄰接鏈及 v2 的鄰接鏈weight, info;
}
Vertex {firstedge; // 指向該頂點的第一條邊（EdgeNode）
}

優點

每條無向邊僅存儲一次，節省空間（對某些實現與場景）。
刪除邊時只需操作一個邊節點，便于維護一致性。
遍歷頂點鄰居仍然高效，時間隨度增長。

缺點

實現稍復雜（邊節點需要兩個鄰接指針）。
在需要為邊賦予方向屬性或在有向圖上使用時不適用。

復雜度

空間：O(n + m)
枚舉鄰居：O(\deg(v))
插入邊：O(1)
刪除邊：在已知位置可為 O(1)，否則需找到前驅。

適用場景

無向圖中希望使每條邊只存一次的場景。
圖操作（刪除、修改邊）要求單點一致性的場景。

Java樸素實現

/*** 無向圖的鄰接多重表存儲表示*/
public class AdjacencyMultilistGraph<V,E> {public static final int MAX_VERTEX_NUM = 20;
?public VexBox<V,E>[] adjmulist; // 鄰接多重表public int vexnum; ? ? ? ? ?// 當前頂點數public int edgenum; ? ? ? ? // 當前邊數
?@SuppressWarnings("unchecked")public AdjacencyMultilistGraph() {this.adjmulist = (VexBox<V, E>[]) new VexBox<?,?>[MAX_VERTEX_NUM];this.vexnum = 0;this.edgenum = 0;}
?public static class EBox<E> {public int iVex; ? ? ? ?// 該邊依附的兩個頂點的位置public int jVex; ? ? ? ?// 該邊依附的兩個頂點的位置public EBox<E> iLink; ? // 指向依附頂點iVex的下一條邊public EBox<E> jLink; ? // 指向依附頂點jVex的下一條邊public E info; ? ? ? ? ?// 該邊信息指針}
?public static class VexBox<V,E> {public V data; ? ? ? ? ? ? ?// 頂點數據public EBox<E> firstedge; ? // 指向第一條依附該頂點的邊}
?
}

6 關聯矩陣（Incidence Matrix / 關聯矩陣）

定義與結構 關聯矩陣是 n \times m 的矩陣，行表示頂點，列表示邊。對于無向圖，如果邊 e_j 連接頂點 v_i，則 B[i][j] = 1（或其他標記，如端點編號）；對于有向圖可以用 1 表示出端點，-1 表示入端點（或用 1/0 和方向表述）。

舉例（有向圖）若第 j 條邊從 v_p 指向 v_q，則 B[p][j] = 1，B[q][j] = -1，其他行為 0。

優點

適合處理邊與頂點之間的“關系”分析（如網絡流基礎理論、線性代數方法）。
在某些數學分析（如圖的循環空間、切空間）中方便用線性代數處理。

缺點

空間復雜度 O(nm)，對大型圖不友好（尤其當邊數 m 很大時）。
枚舉鄰接關系較為低效（需要掃描對應列或行）。
一般用于理論分析或非常特殊的算法場景，在工程實現中較少單獨使用。

復雜度

空間：O(nm)
通過矩陣計算可得到路徑關系等，但代價昂貴。

適用場景

圖的代數性質分析（如環空間、基循環、切空間）。
網絡流中部分數學建模。

Java樸素實現

/*** 圖的關聯矩陣表示*/
public class IncidenceMatrixGraph<V,E> {public static final int MAX_VERTEX_NUM = 20;public static final int MAX_EDGE_NUM = 100;
?// 頂點數組public Vertex<V>[] vertices;
?// 邊數組（只存儲邊數據，不存儲端點信息）public Edge<E>[] edges;
?// 關聯矩陣：表達頂點與邊的關聯關系public int[][] matrix;
?// 當前頂點數和邊數public int vernum;public int edgenum;
?// 圖類型：0-無向圖，1-有向圖public int graphType;
?public IncidenceMatrixGraph(int graphType) {this.vertices = (Vertex<V>[])new Vertex<?>[MAX_VERTEX_NUM];this.edges = (Edge<E>[])new Edge<?>[MAX_EDGE_NUM];this.matrix = new int[MAX_VERTEX_NUM][MAX_EDGE_NUM];this.vernum = 0;this.edgenum = 0;this.graphType = graphType;}
?public static class Vertex<V> {V data;public Vertex(V data) {this.data = data;}}
?// 邊只存儲自身數據，端點信息由矩陣表達public static class Edge<E> {E data;public Edge(E data) {this.data = data;}}
}

二圖的 RDBMS 建模

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

1 建模基本思路

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

頂點表（Vertex Table）：存儲圖中的所有節點；
邊表（Edge Table）：存儲圖中所有的邊（連接關系）;
標簽表（Label Table）: 存儲頂點和邊的標簽信息；

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），可使用以下兩種策略之一：

對稱存儲：每條邊存儲兩次，分別是 (u → v) 和 (v → u)；
約束存儲順序：強制存儲一次，并約定 from_vertex < to_vertex，查詢時統一處理對稱性。

三圖算法基礎數據結構-鄰接表

在前文我們已經介紹了圖的多種數據結構表示方式（鄰接矩陣、鄰接表、邊列表、十字鏈表、鄰接多重表、關聯矩陣），并且給出了其Java的樸素實現。在進入后續的圖算法部分之前，有必要確定一種在算法實現中最常用的數據結構作為統一輸入。實踐中，鄰接表（Adjacency List） 因其存儲效率高、空間利用率好、便于圖遍歷與路徑搜索，被廣泛用于圖算法的實現。因此，本節我們將詳細介紹一個面向后續算法實現的鄰接表對象建模與代碼示例。

1 鄰接表建模思路

在圖的抽象建模中，我們至少需要三個核心要素：

頂點（Vertex）：表示對象實體，可以附帶標簽（如類型）和屬性信息。
邊（Edge）：表示對象之間的關系，通常包含權重、方向、標簽和屬性。
圖（Graph）：由一組頂點和邊構成，提供統一的訪問與管理接口。

此外，還需要一個標簽類（Label），用來區分不同類型的頂點和邊。這種抽象設計不僅符合圖論的基本定義，同時為后續復雜算法（如最短路徑、拓撲排序、強連通分量分解等）的實現提供了良好的擴展性。

2 代碼實現

下面的 Java 代碼示例展示了如何用面向對象方式構建鄰接表：

(1) 標簽類 `Label`

import java.util.concurrent.atomic.AtomicInteger;
?
public class Label {private static final AtomicInteger labelIdCounter = new AtomicInteger(0);
?private Integer id; ? ? ? ?// 隱式ID，自增private String label; ? ? ?// 標簽名稱private Integer category; ?// 1-頂點  2-邊
?public Label(String label, Integer category) {this.id = genId();this.label = label;this.category = category;}
?public int getId() {return id;}
?public String getLabel() {return label;}
?public void setLabel(String label) {this.label = label;}
?public Integer getCategory() {return category;}
?public void setCategory(Integer category) {this.category = category;}
?private int genId() {return labelIdCounter.getAndIncrement();}
?// 分類枚舉enum Category {VERTEX(1), EDGE(2);Integer id;Category(int id) {this.id = id;}}
}

該類為頂點和邊賦予標簽及唯一 ID，方便后續分類和檢索。

(2) 頂點類 `Vertex`

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
?
public class Vertex {private static final AtomicInteger nodeIdCounter = new AtomicInteger(0);
?private Integer id; ? ? ? ? ? ? ? // 頂點IDprivate String name; ? ? ? ? ? ? ?// 頂點顯示名稱private Label label; ? ? ? ? ? ? ?// 頂點標簽private Map<String, Object> properties; // 頂點屬性private Map<Integer, Edge> edgeList; ? ?// 鄰接邊列表
?public Vertex(String name, Label label) {this.id = genId();this.name = name;this.label = label;this.properties = new HashMap<>();this.edgeList = new HashMap<>();}
?public Integer getId() {return id;}
?public String getName() {return name;}
?public Label getLabel() {return label;}
?public Map<String, Object> getProperties() {return properties;}
?public List<Edge> getEdgeList() {return new ArrayList<>(this.edgeList.values());}
?public Object getProperty(String key) {return this.properties.get(key);}public void setProperty(String key, Object value) {this.properties.put(key, value);}
?private int genId() {return nodeIdCounter.getAndIncrement();}
?// 添加鄰接邊public void addEdge(Edge edge) {this.edgeList.put(edge.getId(), edge);}
?public void addEdge(Vertex to, int weight, Label label) {Edge edge = new Edge(this, to, weight, label);this.edgeList.put(edge.getId(), edge);}
}

頂點類不僅保存了名稱與標簽，還維護了與其相連的邊集合（鄰接表的核心結構）。

(3) 邊類 `Edge`

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
?
public class Edge {private static final AtomicInteger edgeIdCounter = new AtomicInteger(0);
?private Integer id; ? ? ? ? ? ? // 邊IDprivate Vertex from; ? ? ? ? ? ?// 起始頂點private Vertex to; ? ? ? ? ? ? ?// 目標頂點private Label label; ? ? ? ? ? ?// 邊標簽private Integer weight; ? ? ? ? // 邊權重private Map<String, Object> properties; // 邊屬性
?public Edge(Vertex from, Vertex to, int weight, Label label) {this.id = genId();this.from = from;this.to = to;this.label = label;this.weight = weight;this.properties = new HashMap<>();}
?public Integer getId() {return id;}
?public Vertex getFrom() {return from;}
?public Vertex getTo() {return to;}
?public Label getLabel() {return label;}
?public Integer getWeight() {return weight;}
?public Map<String, Object> getProperties() {return properties;}
?public Object getProperty(String key) {return this.properties.get(key);}
?public void setProperty(String key, Object value) {this.properties.put(key, value);}
?private int genId() {return edgeIdCounter.getAndIncrement();}
}

該類定義了邊的基本信息，包括權重與屬性信息，支持靈活擴展。

(4) 圖類 `AdjacencyGraph`

import java.util.HashMap;
import java.util.Map;
?
public class AdjacencyGraph {private Map<Integer, Vertex> vertices;private Integer vertexNum;private Integer edgeNum;
?public AdjacencyGraph() {vertices = new HashMap<>();vertexNum = 0;edgeNum = 0;}
?public Map<Integer, Vertex> getVertices() {return vertices;}
?public Integer getVertexNum() {return vertexNum;}
?public Integer getEdgeNum() {return edgeNum;}
?// 添加頂點public void addVertex(Vertex v) {vertices.put(v.getId(), v);vertexNum++;}
?// 添加邊public void addEdge(Edge edge) {edge.getFrom().addEdge(edge);edgeNum++;}
}

圖類 AdjacencyGraph 用來維護全局的頂點與邊集合，并且通過鄰接表結構保證每個頂點能快速訪問其鄰接點。

3 說明

鄰接表不僅是算法輸入的常用數據結構，同時也非常貼合現實世界的圖數據存儲需求。通過 Label、Vertex、Edge、AdjacencyGraph 的建模，我們能夠清晰地表達圖的各個組成部分，并為后續的圖算法實現（如深度優先搜索、廣度優先搜索、Dijkstra 最短路徑、Prim/Kruskal 最小生成樹等）提供了統一的數據接口。