跳到主要内容

图的高级表示

图（Graph）是一种非常重要的数据结构，用于表示对象之间的关系。图由**顶点（Vertex）和边（Edge）**组成，顶点表示对象，边表示对象之间的关系。在实际应用中，图可以用于建模社交网络、交通网络、推荐系统等复杂关系。

为了更好地表示图，我们需要掌握几种高级的表示方法。本文将详细介绍邻接表、邻接矩阵和边列表这三种常见的图表示方法，并通过实际案例帮助你理解它们的应用场景。

1. 邻接表（Adjacency List）​

邻接表是图的一种常见表示方法，特别适合表示稀疏图（即边的数量远少于顶点数量的平方）。邻接表的核心思想是为每个顶点维护一个列表，列表中存储与该顶点直接相连的其他顶点。

邻接表的实现​

以下是一个用 Python 实现的邻接表示例：

# 使用字典表示邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 打印邻接表
for vertex, neighbors in graph.items():
    print(f"{vertex}: {neighbors}")

输入：

  • 图的顶点和边关系如上代码所示。

输出：

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'F']
D: ['B']
E: ['B', 'F']
F: ['C', 'E']

邻接表的优缺点​

  • 优点：
    • 空间效率高，适合稀疏图。
    • 查找某个顶点的邻居非常高效。
  • 缺点：
    • 查找两个顶点之间是否有边需要遍历列表，效率较低。

2. 邻接矩阵（Adjacency Matrix）​

邻接矩阵是另一种常见的图表示方法，适合表示稠密图（即边的数量接近顶点数量的平方）。邻接矩阵是一个二维数组，其中 matrix[i][j] 表示顶点 i 和顶点 j 之间是否有边。

邻接矩阵的实现​

以下是一个用 Python 实现的邻接矩阵示例：

# 使用二维列表表示邻接矩阵
graph = [
    [0, 1, 1, 0, 0, 0],  # A
    [1, 0, 0, 1, 1, 0],  # B
    [1, 0, 0, 0, 0, 1],  # C
    [0, 1, 0, 0, 0, 0],  # D
    [0, 1, 0, 0, 0, 1],  # E
    [0, 0, 1, 0, 1, 0]   # F
]

# 打印邻接矩阵
for row in graph:
    print(row)

输入：

  • 图的顶点和边关系如上代码所示。

输出：

[0, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 0]
[1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0]

邻接矩阵的优缺点​

  • 优点：
    • 查找两个顶点之间是否有边非常高效。
    • 适合表示稠密图。
  • 缺点：
    • 空间复杂度高，为 O(V^2)，其中 V 是顶点数量。
    • 对于稀疏图来说，浪费了大量空间。

3. 边列表（Edge List）​

边列表是一种简单的图表示方法，直接存储图中的所有边。每条边用一个元组或列表表示，包含两个顶点。

边列表的实现​

以下是一个用 Python 实现的边列表示例：

# 使用列表存储边
edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('B', 'E'),
    ('C', 'F'),
    ('E', 'F')
]

# 打印边列表
for edge in edges:
    print(edge)

输入：

  • 图的顶点和边关系如上代码所示。

输出：

('A', 'B')
('A', 'C')
('B', 'D')
('B', 'E')
('C', 'F')
('E', 'F')

边列表的优缺点​

  • 优点：
    • 实现简单，适合存储边的信息。
    • 适合某些特定算法（如 Kruskal 的最小生成树算法）。
  • 缺点：
    • 查找某个顶点的邻居需要遍历所有边，效率较低。

实际应用案例​

案例 1：社交网络​

在社交网络中，用户是顶点，用户之间的关系（如好友关系）是边。邻接表非常适合表示这种稀疏图，因为每个用户的好友数量通常远少于总用户数。

案例 2：交通网络​

在交通网络中，城市是顶点，城市之间的道路是边。邻接矩阵适合表示这种稠密图，因为城市之间的道路通常比较密集。

总结​

图的高级表示方法包括邻接表、邻接矩阵和边列表，每种方法都有其优缺点和适用场景：

  • 邻接表：适合稀疏图，空间效率高。
  • 邻接矩阵：适合稠密图，查找边的效率高。
  • 边列表：实现简单，适合存储边的信息。

选择合适的表示方法可以显著提高算法的效率和性能。

附加资源与练习​

练习​

  1. 使用邻接表表示一个包含 5 个顶点的图，并打印其邻接表。
  2. 使用邻接矩阵表示一个包含 4 个顶点的图，并打印其邻接矩阵。
  3. 使用边列表表示一个包含 3 个顶点的图，并打印其边列表。

资源​