三种建图方式Python实现

目录

概述

在图论算法中，如何高效地存储图结构是至关重要的。常见的建图方式有三种：

• 邻接矩阵：适合稠密图，查询快
• 邻接表：适合稀疏图，节省空间
• 链式前向星：竞赛常用，效率高

邻接矩阵

核心思想

使用二维数组 graph[i][j] 表示从点 i 到点 j 的边权。

代码实现

"""
使用邻接矩阵建立有向图和无向图
邻接矩阵适合稠密图，空间复杂度 O(n²)
"""

# 点的最大数量
MAXN = 11

# 邻接矩阵
graph = [[0] * MAXN for _ in range(MAXN)]

def build(n):
"""初始化建图，清空邻接矩阵"""
for i in range(1, n + 1):
for j in range(1, n + 1):
graph[i][j] = 0

def add_direct_edge(u, v, w):
"""添加有向边 u -> v，权重为 w"""
graph[u][v] = w

def add_undirect_edge(u, v, w):
"""添加无向边 u – v，权重为 w"""
graph[u][v] = w
graph[v][u] = w

def direct_graph(n, edges):
"""建立有向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
add_direct_edge(u, v, w)

def undirect_graph(n, edges):
"""建立无向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
add_undirect_edge(u, v, w)

def traversal(n):
"""遍历并打印邻接矩阵"""
print("邻接矩阵 (行->列的边权，0 表示无边):")
for i in range(1, n + 1):
for j in range(1, n + 1):
print(f"{graph[i][j]:3}", end=" ")
print()

def get_neighbors(u, n):
"""获取点 u 的所有邻居及其边权"""
neighbors = []
for v in range(1, n + 1):
if graph[u][v] != 0:
neighbors.append((v, graph[u][v]))
return neighbors

使用示例

# 有向带权图
n = 4
edges = [[1, 3, 6], [4, 3, 4], [2, 4, 2],
[1, 2, 7], [2, 3, 5], [3, 1, 1]]
direct_graph(n, edges)
traversal(n)

# 获取邻居
neighbors = get_neighbors(1, n) # [(2, 7), (3, 6)]

优缺点

优点：

• ✅ 查询两点间是否有边：O(1)
• ✅ 实现简单直观
• ✅ 适合稠密图

缺点：

• ❌ 空间复杂度 O(n²)，浪费空间
• ❌ 遍历某个点的邻居：O(n)

邻接表

核心思想

使用列表存储每个点的所有邻居。有两种实现方式：

方式 1：传统列表实现

"""
使用邻接表建立有向图和无向图
邻接表适合稀疏图，空间复杂度 O(n + m)
"""

# 点的最大数量
MAXN = 11

# 邻接表：graph[u] 存储 u 的所有出边邻居 (v, w)
graph = [[] for _ in range(MAXN)]

def build(n):
"""初始化建图，清空邻接表"""
for i in range(MAXN):
graph[i] = []

def add_direct_edge(u, v, w):
"""添加有向边 u -> v，权重为 w"""
graph[u].append((v, w))

def add_undirect_edge(u, v, w):
"""添加无向边 u – v，权重为 w"""
graph[u].append((v, w))
graph[v].append((u, w))

def direct_graph(n, edges):
"""建立有向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
add_direct_edge(u, v, w)

def undirect_graph(n, edges):
"""建立无向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
add_undirect_edge(u, v, w)

def traversal(n):
"""遍历并打印邻接表"""
print("邻接表 (点： (邻居，边权)):")
for i in range(1, n + 1):
print(f"{i}: ", end="")
for neighbor in graph[i]:
print(f"({neighbor[0]}, {neighbor[1]}) ", end="")
print()

def get_neighbors(u):
"""获取点 u 的所有邻居及其边权"""
return graph[u]

def get_degree(u):
"""获取点 u 的度（出边数量）"""
return len(graph[u])

方式 2：defaultdict 实现（推荐）

"""
使用 defaultdict 实现邻接表（推荐方式）
相比传统列表实现，更加 Pythonic 和灵活
"""

from collections import defaultdict

class Graph:
"""使用 defaultdict 实现的图类"""

def __init__(self, directed=False):
"""
初始化图
:param directed: 是否为有向图，默认 False（无向图）
"""
self.directed = directed
# 使用 defaultdict(list) 自动为每个节点创建空列表
self.adj = defaultdict(list)
# 记录所有节点
self.nodes = set()

def add_edge(self, u, v, w=1):
"""
添加边
:param u: 起点
:param v: 终点
:param w: 边权重，默认为 1
"""
self.adj[u].append((v, w))
self.nodes.add(u)
self.nodes.add(v)

# 如果是无向图，需要添加反向边
if not self.directed:
self.adj[v].append((u, w))

def build_from_edges(self, edges):
"""
从边列表批量建图
:param edges: 边的列表 [[u1, v1, w1], [u2, v2, w2], …]
"""
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
self.add_edge(u, v, w)

def neighbors(self, u):
"""
获取节点 u 的所有邻居
:param u: 节点
:return: 邻居列表 [(v1, w1), (v2, w2), …]
"""
return self.adj[u]

def degree(self, u):
"""
获取节点 u 的度（出边数量）
:param u: 节点
:return: 度的数量
"""
return len(self.adj[u])

def all_nodes(self):
"""
获取所有节点
:return: 节点集合
"""
return self.nodes

def traversal(self):
"""遍历并打印邻接表"""
print(f"{'有向' if self.directed else '无向'}图的邻接表：")
for node in sorted(self.nodes):
print(f"{node}: ", end="")
for neighbor in self.adj[node]:
print(f"({neighbor[0]}, {neighbor[1]}) ", end="")
print()

使用示例

# 传统列表实现
n = 4
edges = [[1, 3, 6], [4, 3, 4], [2, 4, 2],
[1, 2, 7], [2, 3, 5], [3, 1, 1]]
direct_graph(n, edges)
traversal(n)

# defaultdict 实现
g = Graph(directed=True)
edges = [[1, 3, 6], [4, 3, 4], [2, 4, 2],
[1, 2, 7], [2, 3, 5], [3, 1, 1]]
g.build_from_edges(edges)
g.traversal()

# 获取邻居
neighbors = g.neighbors(1) # [(3, 6), (2, 7)]

优缺点

传统列表实现：

• ✅ 适合竞赛编程（已知数据范围）
• ❌ 需要预先定义 MAXN
• ❌ 节点编号必须连续

defaultdict 实现：

• ✅ 不需要预先定义大小，自动扩展
• ✅ 节点编号可以不连续
• ✅ 支持任意可哈希的节点类型（字符串、元组等）
• ✅ 更 Pythonic，适合实际项目开发

链式前向星

核心思想

使用数组模拟链表，结合了邻接表和数组的优点。

代码实现

"""
使用链式前向星建立有向图和无向图
链式前向星是一种高效的图存储方式，结合了邻接表和数组的优点
空间复杂度 O(m)，适合稀疏图，遍历效率高
"""

# 点的最大数量
MAXN = 11

# 边的最大数量
# 无向图需要 m*2，因为一条无向边要存两条有向边
MAXM = 21

# head[u]: 点 u 的第一条边的下标
head = [0] * MAXN

# next_arr[e]: 边 e 的下一条边的下标
next_arr = [0] * MAXM

# to[e]: 边 e 指向的终点
to = [0] * MAXM

# weight[e]: 边 e 的权重
weight = [0] * MAXM

# 当前边的下标（从 1 开始）
cnt = 0

def build(n):
"""初始化建图，清空所有数据结构"""
global cnt
cnt = 1
for i in range(1, n + 1):
head[i] = 0

def add_edge(u, v, w):
"""
添加有向边 u -> v，权重为 w
使用头插法，新边插入到链表头部
"""
global cnt
# 新边的 next 指向当前 head[u]（即原来的第一条边）
next_arr[cnt] = head[u]
# 新边的终点是 v
to[cnt] = v
# 新边的权重是 w
weight[cnt] = w
# 更新 head[u] 为新边的下标
head[u] = cnt
# 下标递增
cnt += 1

def direct_graph(n, edges):
"""建立有向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
add_edge(u, v, w)

def undirect_graph(n, edges):
"""建立无向带权图"""
build(n)
for edge in edges:
u, v, w = edge[0], edge[1], edge[2]
# 无向边需要添加两条有向边
add_edge(u, v, w)
add_edge(v, u, w)

def traversal(n):
"""遍历并打印链式前向星"""
print("链式前向星 (点： (邻居，边权)):")
for i in range(1, n + 1):
print(f"{i}: ", end="")
# 从 head[i] 开始遍历所有边
ei = head[i]
while ei > 0:
print(f"({to[ei]}, {weight[ei]}) ", end="")
ei = next_arr[ei]
print()

def get_neighbors(u):
"""获取点 u 的所有邻居及其边权"""
neighbors = []
ei = head[u]
while ei > 0:
neighbors.append((to[ei], weight[ei]))
ei = next_arr[ei]
return neighbors

def get_degree(u):
"""获取点 u 的出度（出边数量）"""
count = 0
ei = head[u]
while ei > 0:
count += 1
ei = next_arr[ei]
return count

使用示例

n = 4
edges = [[1, 3, 6], [4, 3, 4], [2, 4, 2],
[1, 2, 7], [2, 3, 5], [3, 1, 1]]
direct_graph(n, edges)
traversal(n)

# 获取邻居
neighbors = get_neighbors(1) # [(2, 7), (3, 6)]

优缺点

优点：

• ✅ 空间复杂度 O(m)，适合稀疏图
• ✅ 遍历效率高，内存连续
• ✅ 不需要动态分配内存
• ✅ 竞赛编程常用

缺点：

• ❌ 实现稍复杂
• ❌ 需要预先知道边的最大数量
• ❌ 查询两点间是否有边效率低

三种方式对比

数据结构对比

# 邻接矩阵：二维数组
graph = [
[0, 7, 6, 0], # 节点 1
[0, 0, 5, 2], # 节点 2
[1, 0, 0, 0], # 节点 3
[0, 0, 4, 0], # 节点 4
]

# 邻接表：嵌套列表
graph = [
[], # 空索引
[(2, 7), (3, 6)], # 节点 1
[(4, 2), (3, 5)], # 节点 2
[(1, 1)], # 节点 3
[(3, 4)], # 节点 4
]

# 邻接表：defaultdict
graph = {
1: [(2, 7), (3, 6)],
2: [(4, 2), (3, 5)],
3: [(1, 1)],
4: [(3, 4)],
}

# 链式前向星：数组模拟链表
head = [0, 3, 5, 7, 8] # 每个点的第一条边
next_arr = [0, 2, 0, 1, 0, 4, 0, 6, 0] # 下一条边
to = [0, 2, 3, 4, 3, 1, 3, 3, 0] # 终点
weight = [0, 7, 6, 2, 5, 1, 4, 4, 0] # 权重

实战建议

选择指南

1. 竞赛编程

# 已知数据范围，节点数 ≤ 1000
if n <= 1000:
# 使用邻接矩阵，实现简单
graph = [[0] * (n + 1) for _ in range(n + 1)]
else:
# 使用链式前向星，效率高
head = [0] * (n + 1)
next_arr = [0] * (m * 2 + 1)
to = [0] * (m * 2 + 1)
weight = [0] * (m * 2 + 1)

2. 实际项目开发

# 使用 defaultdict，灵活且 Pythonic
from collections import defaultdict

class Graph:
def __init__(self, directed=False):
self.adj = defaultdict(list)
self.nodes = set()

def add_edge(self, u, v, w=1):
self.adj[u].append((v, w))
self.nodes.add(u)
self.nodes.add(v)

3. 需要快速查询边

# 使用 set 实现 O(1) 查询
from collections import defaultdict

class GraphWithSet:
def __init__(self):
self.adj = defaultdict(set)

def add_edge(self, u, v):
self.adj[u].add(v)

def has_edge(self, u, v):
return v in self.adj[u] # O(1)

应用场景

总结

选择哪种建图方式取决于：

• 图的稠密程度
• 是否需要快速查询边
• 节点编号是否连续
• 个人偏好和项目需求

掌握这三种建图方式，就能应对绝大多数图论问题！