鄰接表是圖數據結構的一種高效表示方法，特別適合表示稀疏圖。下面我將用 Python 詳細講解鄰接表的多種實現方式、操作方法和實際應用。

一、鄰接表基礎概念

鄰接表的核心思想是為圖中的每個頂點維護一個列表，存儲與該頂點直接相連的所有鄰接頂點。

鄰接表 vs 鄰接矩陣

特性	鄰接表	鄰接矩陣
空間復雜度	O(V+E)	O(V2)
檢查兩頂點是否相鄰	O(degree(V))	O(1)
獲取所有鄰接點	O(1)	O(V)
添加邊	O(1)	O(1)
刪除邊	O(degree(V))	O(1)

二、Python 鄰接表實現方式

1. 基礎列表實現（無向圖）

class Graph:def __init__(self, num_vertices):self.num_vertices = num_verticesself.adj_list = [[] for _ in range(num_vertices)]def add_edge(self, u, v):"""添加無向邊 u-v"""self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for i in range(self.num_vertices):print(f"頂點 {i} 的鄰接點: {self.adj_list[i]}")# 使用示例
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()

2. 使用 defaultdict（動態頂點）

python

復制

from collections import defaultdictclass Graph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v):"""添加無向邊 u-v"""self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for vertex in self.adj_list:print(f"頂點 {vertex} 的鄰接點: {self.adj_list[vertex]}")# 使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.print_graph()

3. 加權圖實現

python

復制

from collections import defaultdictclass WeightedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight):"""添加加權無向邊 u-v"""self.adj_list[u].append((v, weight))self.adj_list[v].append((u, weight))def print_graph(self):for vertex in self.adj_list:connections = [f"{v}({w})" for v, w in self.adj_list[vertex]]print(f"頂點 {vertex} 的連接: {', '.join(connections)}")# 使用示例
wg = WeightedGraph()
wg.add_edge(0, 1, 4)
wg.add_edge(0, 2, 1)
wg.add_edge(1, 2, 2)
wg.add_edge(1, 3, 5)
wg.print_graph()

三、鄰接表的高級操作

1. 有向圖實現

python

復制

class DirectedGraph:def __init__(self, num_vertices):self.num_vertices = num_verticesself.adj_list = [[] for _ in range(num_vertices)]def add_edge(self, u, v):"""添加有向邊 u→v"""self.adj_list[u].append(v)def reverse(self):"""反轉圖中所有邊的方向"""reversed_graph = DirectedGraph(self.num_vertices)for u in range(self.num_vertices):for v in self.adj_list[u]:reversed_graph.add_edge(v, u)return reversed_graphdef print_graph(self):for i in range(self.num_vertices):print(f"頂點 {i} 指向: {self.adj_list[i]}")# 使用示例
dg = DirectedGraph(4)
dg.add_edge(0, 1)
dg.add_edge(0, 2)
dg.add_edge(1, 2)
dg.add_edge(2, 0)
dg.add_edge(2, 3)
dg.print_graph()

2. 刪除邊和頂點

python

復制

class AdvancedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v):self.adj_list[u].append(v)self.adj_list[v].append(u)def remove_edge(self, u, v):"""刪除無向邊 u-v"""if v in self.adj_list[u]:self.adj_list[u].remove(v)self.adj_list[v].remove(u)def remove_vertex(self, u):"""刪除頂點及其所有邊"""for v in self.adj_list[u]:self.adj_list[v].remove(u)del self.adj_list[u]def print_graph(self):for vertex in self.adj_list:print(f"頂點 {vertex} 的鄰接點: {self.adj_list[vertex]}")# 使用示例
ag = AdvancedGraph()
ag.add_edge(0, 1)
ag.add_edge(0, 2)
ag.add_edge(1, 2)
ag.add_edge(2, 3)
print("原始圖:")
ag.print_graph()ag.remove_edge(1, 2)
print("\n刪除邊1-2后:")
ag.print_graph()ag.remove_vertex(2)
print("\n刪除頂點2后:")
ag.print_graph()

四、鄰接表的實際應用

1. 廣度優先搜索(BFS)

python

復制

from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:vertex = queue.popleft()print(vertex, end=" ")for neighbor in graph.adj_list[vertex]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)# 使用示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)print("BFS遍歷從頂點2開始:")
bfs(g, 2)

2. 深度優先搜索(DFS)

python

復制

def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start, end=" ")for neighbor in graph.adj_list[start]:if neighbor not in visited:dfs(graph, neighbor, visited)# 使用示例
print("\nDFS遍歷從頂點2開始:")
dfs(g, 2)

3. 檢測圖中是否有環

python

復制

def has_cycle(graph):visited = set()def dfs_util(vertex, parent):visited.add(vertex)for neighbor in graph.adj_list[vertex]:if neighbor not in visited:if dfs_util(neighbor, vertex):return Trueelif neighbor != parent:return Truereturn Falsefor vertex in graph.adj_list:if vertex not in visited:if dfs_util(vertex, -1):return Truereturn False# 使用示例
cycle_graph = Graph(3)
cycle_graph.add_edge(0, 1)
cycle_graph.add_edge(1, 2)
cycle_graph.add_edge(2, 0)no_cycle_graph = Graph(3)
no_cycle_graph.add_edge(0, 1)
no_cycle_graph.add_edge(1, 2)print("\n圖中是否有環:")
print("cycle_graph:", has_cycle(cycle_graph))
print("no_cycle_graph:", has_cycle(no_cycle_graph))

五、性能優化技巧

1. ?使用集合代替列表?：如果需要頻繁檢查邊的存在性

   python

   復制

   self.adj_list = defaultdict(set)  # 使用集合存儲鄰接點

2. ?預分配空間?：已知頂點數量時

   python

   復制

   self.adj_list = [None] * num_vertices
   for i in range(num_vertices):self.adj_list[i] = []

3. ?使用更高效的數據結構?：如?array.array?或?numpy.ndarray?處理大型圖

4. ?并行處理?：對大型圖的操作可以使用多線程/多進程

六、常見問題解答

?Q: 如何表示帶權重的有向圖？??

A: 可以使用字典存儲權重信息：

python

復制

class WeightedDirectedGraph:def __init__(self):self.adj_list = defaultdict(list)def add_edge(self, u, v, weight):self.adj_list[u].append((v, weight))def print_graph(self):for vertex in self.adj_list:connections = [f"{v}({w})" for v, w in self.adj_list[vertex]]print(f"頂點 {vertex} 指向: {', '.join(connections)}")

?Q: 如何處理頂點不是整數的情況？??

A: 可以使用字典映射：

python

復制

class NamedGraph:def __init__(self):self.adj_list = defaultdict(list)self.vertex_index = {}self.index_vertex = {}self.counter = 0def add_vertex(self, name):if name not in self.vertex_index:self.vertex_index[name] = self.counterself.index_vertex[self.counter] = nameself.counter += 1def add_edge(self, u_name, v_name):self.add_vertex(u_name)self.add_vertex(v_name)u = self.vertex_index[u_name]v = self.vertex_index[v_name]self.adj_list[u].append(v)self.adj_list[v].append(u)def print_graph(self):for i in range(self.counter):name = self.index_vertex[i]neighbors = [self.index_vertex[v] for v in self.adj_list[i]]print(f"頂點 {name} 的鄰接點: {neighbors}")

通過以上詳細的 Python 實現，你應該能夠全面掌握鄰接表的構建方法和各種操作技巧。根據你的具體應用場景，可以選擇最適合的實現方式。