第 38 课 - 图的表示

学习目标

理解图的基本概念：顶点（Vertex）和边（Edge）。
掌握两种核心的图表示方法：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。
能够使用编程语言实现这两种表示方法，并进行基本的图操作（如添加边、查询连接）。
分析并比较两种表示方法的时间复杂度和空间复杂度，理解其适用场景。

核心概念

想象一下城市的地铁网络：每个站点是一个“顶点”（Vertex），连接两个站点的地铁线路就是“边”（Edge）。图（Graph）就是用来表示这种多对多关系的数学模型。为了让计算机理解并处理图，我们需要用特定的数据结构来“表示”它。

我们重点学习两种最常用的表示方法：

邻接矩阵 (Adjacency Matrix) 这是一种直观的二维表格方法。我们创建一个 N x N 的矩阵（N是顶点的数量），如果顶点 i 和顶点 j 之间有一条边，就把矩阵中第 i 行第 j 列的元素设为 1（或权重），否则设为 0。

优点：
- 判断两个顶点是否相连非常快（时间复杂度 O(1)）。
- 实现简单。
缺点：
- 空间占用大，无论有多少边，都需要 N^2 的空间。对于稀疏图（边很少）来说非常浪费。
- 遍历一个顶点的所有邻居，需要扫描整行，时间复杂度为 O(N)。
邻接表 (Adjacency List) 这是更节省空间的方法。我们为每个顶点维护一个列表，列表中存放着所有与它直接相连的顶点。通常使用一个数组（或字典），数组的每个索引对应一个顶点，其值是一个链表（或动态数组），存储该顶点的所有邻居。

优点：
- 节省空间，只存储实际存在的边。空间复杂度为 O(N+E)，E是边的数量。
- 遍历一个顶点的所有邻居非常高效，只需遍历其对应的列表。
缺点：
- 判断两个顶点 i 和 j 是否相连，需要搜索顶点 i 的邻接表，时间复杂度为 O(degree(i))，其中 degree(i) 是顶点 i 的度数（邻居数量）。

代码示例

我们使用Python来实现一个无向图（边是双向的）的两种表示。

1. 邻接矩阵实现

class GraphAdjMatrix:
    def __init__(self, num_vertices):
        """初始化图，创建一个全0的N x N矩阵"""
        self.num_vertices = num_vertices
        # 初始化一个num_vertices行，num_vertices列的二维列表，所有元素初始为0
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, v1, v2):
        """在顶点v1和v2之间添加一条边（无向图，所以双向设置）"""
        if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices:
            self.matrix[v1][v2] = 1
            self.matrix[v2][v1] = 1  # 因为是无向图
        else:
            print(f"错误：顶点 {v1} 或 {v2} 超出范围 (0-{self.num_vertices-1})")

    def print_matrix(self):
        """打印邻接矩阵"""
        print("邻接矩阵:")
        for row in self.matrix:
            print(row)

# 使用示例
g = GraphAdjMatrix(4)  # 创建一个包含4个顶点(0,1,2,3)的图
g.add_edge(0, 1)       # 添加边 0-1
g.add_edge(0, 2)       # 添加边 0-2
g.add_edge(1, 2)       # 添加边 1-2
g.add_edge(2, 3)       # 添加边 2-3
g.print_matrix()

# 查询顶点1和3是否相连
print(f"\n顶点1和3相连吗？ {'是' if g.matrix[1][3] == 1 else '否'}")
print(f"顶点0和1相连吗？ {'是' if g.matrix[0][1] == 1 else '否'}")

输出：

邻接矩阵:
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 0, 1]
[0, 0, 1, 0]

顶点1和3相连吗？ 否
顶点0和1相连吗？ 是

2. 邻接表实现

class GraphAdjList:
    def __init__(self, num_vertices):
        """初始化图，创建一个包含N个空列表的数组"""
        self.num_vertices = num_vertices
        # 初始化一个列表，每个元素是另一个列表，用于存储邻居
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, v1, v2):
        """在顶点v1和v2之间添加一条边（无向图）"""
        if 0 <= v1 < self.num_vertices and 0 <= v2 < self.num_vertices:
            # 将v2添加到v1的邻接表中
            self.adj_list[v1].append(v2)
            # 将v1添加到v2的邻接表中（因为是无向图）
            self.adj_list[v2].append(v1)
        else:
            print(f"错误：顶点 {v1} 或 {v2} 超出范围 (0-{self.num_vertices-1})")

    def print_list(self):
        """打印邻接表"""
        print("邻接表:")
        for i in range(self.num_vertices):
            print(f"顶点 {i}: {self.adj_list[i]}")

# 使用示例
g = GraphAdjList(4)  # 创建一个包含4个顶点(0,1,2,3)的图
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_list()

# 查询顶点0的邻居
print(f"\n顶点0的邻居是: {g.adj_list[0]}")
# 判断顶点1和3是否相连
if 3 in g.adj_list[1]: # 在列表中搜索
    print("顶点1和3相连")
else:
    print("顶点1和3不相连")

输出：

邻接表:
顶点 0: [1, 2]
顶点 1: [0, 2]
顶点 2: [0, 1, 3]
顶点 3: [2]

顶点0的邻居是: [1, 2]
顶点1和3不相连

实践练习

基础练习：使用 GraphAdjList 类，创建一个包含5个顶点（0-4）的图，并添加边：(0,1), (0,4), (1,2), (1,3), (2,3), (3,4)。编写代码打印出每个顶点的度数（即其邻居的数量）。
比较练习：对于上面练习1创建的图，分别用 GraphAdjMatrix 和 GraphAdjList 来表示。假设顶点编号从0到4，请估算并写下这两种表示各需要存储多少个“数字”（矩阵需要存储N*N个数字，邻接表需要存储2E个数字，E是边数）。哪种方式更节省空间？为什么？
进阶练习：尝试修改 GraphAdjList 类，使其能够表示一个带权无向图。即每条边都有一个权重（例如距离、时间）。提示：邻接表的每个列表元素需要同时存储邻居顶点和对应的权重。你可以将每个邻居项存储为一个元组 (neighbor, weight)。实现 add_edge(v1, v2, weight) 方法，并添加一个方法 print_weighted_list() 来打印带权邻接表。

常见错误

无向图的单边设置：在无向图中，边 (A, B) 和 (B, A) 是等同的。使用邻接矩阵或邻接表时，必须确保 双向都进行了设置。只设置 matrix[A][B]=1 而忘记 matrix[B][A]=1，会导致图的信息不完整。
顶点编号混淆：在编程中，顶点通常从0开始编号。如果你的逻辑是1-based（从1开始），必须小心索引越界。例如，一个包含5个顶点的图，顶点编号应为0-4，而不是1-5。
忽略权重图：本课示例是无权图。如果遇到带权图（如最短路径问题），邻接矩阵应存储权重值（而不仅仅是0/1），邻接表需要存储 (邻居, 权重) 对。

小结

本课我们学习了如何在计算机中“画”出一个图：

图的基本元素：顶点是实体，边是实体间的关系。
邻接矩阵：用一个二维表格记录所有顶点间的连接情况。查询快，但空间开销大，适合稠密图（边很多）。
邻接表：为每个顶点列一个“好友列表”。空间效率高，尤其适合稀疏图（边相对较少），是实践中更常用的方法。
选择依据：根据图的稀疏程度、主要操作（是频繁查询连接，还是遍历邻居）来权衡选择哪种表示方法。

理解这两种表示方法，是学习后续所有图算法（如遍历、最短路径、连通性检测）的坚实基础。下一课，我们将学习如何“访问”图中的每一个顶点，从深度优先搜索（DFS）开始。

练习编辑器

rust