树与图 3.4 图的表示方法（邻接矩阵与邻接表）

在计算机科学中，图是一种重要的数据结构，用于表示对象之间的关系。图由顶点（或节点）和边组成，边连接顶点。图的表示方法有多种，其中最常用的两种是邻接矩阵和邻接表。本文将详细介绍这两种表示方法，包括它们的优缺点、适用场景以及示例代码。

1. 邻接矩阵

1.1 定义

邻接矩阵是一个二维数组，用于表示图中顶点之间的连接关系。对于一个有 ( n ) 个顶点的图，邻接矩阵是一个 ( n \times n ) 的矩阵，其中矩阵的元素 ( matrix[i][j] ) 表示顶点 ( i ) 和顶点 ( j ) 之间是否存在边。

对于无向图，如果存在边 ( (i, j) )，则 ( matrix[i][j] = 1 ) 和 ( matrix[j][i] = 1 )。
对于有向图，如果存在边 ( (i, j) )，则 ( matrix[i][j] = 1 )，而 ( matrix[j][i] = 0 )。

1.2 示例

假设我们有一个无向图，包含 4 个顶点和 4 条边，如下所示：

该图的邻接矩阵表示如下：

    0  1  2  3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 1, 1 ]
2 [ 1, 1, 0, 0 ]
3 [ 0, 1, 0, 0 ]

1.3 优点

快速查询：邻接矩阵可以在 ( O(1) ) 的时间复杂度内判断任意两个顶点之间是否存在边。
简单实现：实现相对简单，适合小规模图的表示。

1.4 缺点

空间复杂度高：对于稀疏图，邻接矩阵会浪费大量空间，因为大部分元素可能是 0。
不适合动态变化：在图的边频繁增加或删除的情况下，邻接矩阵的效率较低。

1.5 示例代码（Python）

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数量
        self.adj_matrix = [[0] * vertices for _ in range(vertices)]  # 初始化邻接矩阵

    def add_edge(self, u, v):
        self.adj_matrix[u][v] = 1  # 添加边
        self.adj_matrix[v][u] = 1  # 无向图，添加反向边

    def display(self):
        for row in self.adj_matrix:
            print(row)

# 示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.display()

2. 邻接表

2.1 定义

邻接表是另一种表示图的方式，它使用一个数组（或列表）来存储每个顶点的邻接边。每个数组元素是一个链表（或其他数据结构），用于存储与该顶点相连的所有顶点。

2.2 示例

对于同样的无向图，邻接表的表示如下：

0: 1 -> 2
1: 0 -> 2 -> 3
2: 0 -> 1
3: 1

2.3 优点

节省空间：对于稀疏图，邻接表比邻接矩阵更节省空间，因为它只存储实际存在的边。
动态性强：在图的边频繁增加或删除的情况下，邻接表的效率较高。

2.4 缺点

查询速度慢：判断任意两个顶点之间是否存在边的时间复杂度为 ( O(V) )，其中 ( V ) 是顶点的度数。
实现复杂：相较于邻接矩阵，邻接表的实现稍微复杂一些。

2.5 示例代码（Python）

class Graph:
    def __init__(self, vertices):
        self.V = vertices  # 顶点数量
        self.adj_list = [[] for _ in range(vertices)]  # 初始化邻接表

    def add_edge(self, u, v):
        self.adj_list[u].append(v)  # 添加边
        self.adj_list[v].append(u)  # 无向图，添加反向边

    def display(self):
        for i in range(self.V):
            print(f"{i}: {' -> '.join(map(str, self.adj_list[i]))}")

# 示例
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.display()

3. 总结

在选择图的表示方法时，需要根据具体的应用场景来决定。邻接矩阵适合于密集图和需要快速查询的场景，而邻接表则更适合于稀疏图和动态变化的图结构。理解这两种表示方法的优缺点，有助于在实际开发中做出更合理的选择。希望本文能为您在图的表示方法上提供清晰的指导。