跳到主要内容

图的表示方法

图（Graph）是一种非常重要的数据结构，用于表示对象之间的关系。图由**顶点（Vertex）和边（Edge）**组成，顶点表示对象，边表示对象之间的关系。图广泛应用于社交网络、地图导航、推荐系统等领域。

在计算机中，图可以通过多种方式表示，最常见的两种方法是邻接矩阵和邻接表。接下来，我们将详细介绍这两种表示方法，并通过代码示例和实际案例帮助你更好地理解。

邻接矩阵​

邻接矩阵是一种使用二维数组表示图的方法。对于一个包含 n 个顶点的图，邻接矩阵是一个 n x n 的矩阵。如果顶点 i 和顶点 j 之间存在边，则矩阵中 matrix[i][j] 的值为 1（或边的权重），否则为 0。

示例​

假设我们有一个包含 4 个顶点的无向图，其邻接矩阵如下：

对应的邻接矩阵为：

ABCD
A0110
B1001
C1001
D0110

代码实现​

以下是使用 Python 实现邻接矩阵的代码：

python
# 定义图的顶点数量
n = 4

# 初始化邻接矩阵
adj_matrix = [[0] * n for _ in range(n)]

# 添加边
adj_matrix[0][1] = 1  # A -> B
adj_matrix[1][0] = 1  # B -> A
adj_matrix[0][2] = 1  # A -> C
adj_matrix[2][0] = 1  # C -> A
adj_matrix[1][3] = 1  # B -> D
adj_matrix[3][1] = 1  # D -> B
adj_matrix[2][3] = 1  # C -> D
adj_matrix[3][2] = 1  # D -> C

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

输出：

[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 0, 1]
[0, 1, 1, 0]
备注

邻接矩阵适合表示稠密图（边数接近顶点数的平方），但对于稀疏图（边数远小于顶点数的平方），邻接矩阵会浪费大量空间。

邻接表​

邻接表是一种使用链表或数组列表表示图的方法。对于每个顶点，邻接表存储与其相邻的顶点列表。这种方法在表示稀疏图时非常高效。

示例​

继续使用前面的无向图，其邻接表表示如下：

  • A: [B, C]
  • B: [A, D]
  • C: [A, D]
  • D: [B, C]

代码实现​

以下是使用 Python 实现邻接表的代码：

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

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

输出：

A: ['B', 'C']
B: ['A', 'D']
C: ['A', 'D']
D: ['B', 'C']
提示

邻接表适合表示稀疏图，因为它只存储实际存在的边，节省了大量空间。

实际应用场景​

社交网络​

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

地图导航​

在地图导航中，地点可以被表示为顶点，道路可以被表示为边。邻接矩阵适合表示这种稠密图，因为地点之间通常有多条道路相连。

总结​

  • 邻接矩阵适合表示稠密图，空间复杂度为 O(n^2)。
  • 邻接表适合表示稀疏图，空间复杂度为 O(n + e)，其中 e 是边的数量。
  • 选择哪种表示方法取决于具体的应用场景和图的性质。

附加资源与练习​

  1. 练习：尝试用邻接矩阵和邻接表表示一个有向图，并比较两者的空间复杂度。
  2. 扩展阅读：学习图的遍历算法（如深度优先搜索和广度优先搜索），并尝试用代码实现。
  3. 挑战：实现一个加权图的邻接表和邻接矩阵表示，并思考如何存储边的权重。

希望这篇内容能帮助你更好地理解图的表示方法！继续加油学习吧！