4 图的表示方法

在数据结构的学习中，图是一个重要的概念。图的表示方法可以直接影响到图的操作效率与复杂度。了解图的表示方法是深入学习图论及其相关算法的基础。本篇将会探讨图的几种常用表示方法，包括邻接矩阵、邻接表以及边集数组，我们将通过案例和代码来对这些表示方法进行详细讨论。

1. 图的基本概念

图 ( G ) 通常表示为 ( G = (V, E) )，其中 ( V ) 是顶点（或节点）的集合，( E ) 是边的集合。边连接顶点对，可以是有向的（方向性）或者无向的（无方向性）。在图中，每个顶点和边都可以有权重（weight），使得图的表示更加丰富和有用。

2. 邻接矩阵

邻接矩阵是一种二维数组，适用于表示稠密图。对于图 ( G ) 中的 ( n ) 个顶点，邻接矩阵 ( A ) 是一个 ( n \times n ) 的矩阵，其中：

• ( A[i][j] = 1 )（或边的权重）表示从顶点 ( i ) 到顶点 ( j ) 有一条边存在
• ( A[i][j] = 0 ) 表示从顶点 ( i ) 到顶点 ( j ) 没有边

示例

考虑一个有向图如下：

A -> B
A -> C
B -> C
C -> A

我们可以使用邻接矩阵来表示该图：

	A	B	C
A	0	1	1
B	0	0	1
C	1	0	0

代码示例

# 邻接矩阵实现
class Graph:
    def __init__(self, num_vertices):
        self.V = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_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(3)
g.add_edge(0, 1)  # A -> B
g.add_edge(0, 2)  # A -> C
g.add_edge(1, 2)  # B -> C
g.add_edge(2, 0)  # C -> A
g.display()

3. 邻接表

邻接表是一种更为高效的图表示方法，适用于稀疏图。它使用一个数组（或字典）来存储每个顶点的邻居列表，每个列表中包含与该顶点相连的所有顶点。

示例

对于上面的有向图，我们可以使用邻接表表示为：

A: B, C
B: C
C: A

代码示例

class Graph:
    def __init__(self):
        self.adj_list = {}

    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.adj_list[u] = []
        self.adj_list[u].append(v)  # 对于无向图，使用 self.adj_list[v].append(u)

    def display(self):
        for vertex, edges in self.adj_list.items():
            print(f'{vertex}: {", ".join(edges)}')

# 创建图
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'C')
g.add_edge('C', 'A')
g.display()

4. 边集数组

边集数组是一种更直接的表示方法，适用于无向图和有向图的混合表示。它将图的所有边表示为一个数组，每条边通过两个顶点编号表示，且可以附加权重信息。

示例

对于同一个图，我们可以将其边集数组表示为：

Edges: (A, B), (A, C), (B, C), (C, A)

代码示例

class Graph:
    def __init__(self):
        self.edges = []

    def add_edge(self, u, v):
        self.edges.append((u, v))  # 对于加权图，可加入权重信息

    def display(self):
        for edge in self.edges:
            print(edge)

# 创建图
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'C')
g.add_edge('C', 'A')
g.display()

5. 小结

在本篇中，我们探讨了不同的图的表示方法，包括邻接矩阵、邻接表和边集数组。每种表示方法都有其适用场景，键入性能和存储效率的考虑。在接下来的章节中，将会介绍图的一些高级算法，例如最短路径算法（Dijkstra和Floyd算法），它们都会在这些表示方法的基础上进行实现与应用。

通过对图的直接表示，我们能更直观地理解算法的实现逻辑。希望大家能对图的表示方法有更深入的了解，并且应用于后续的学习和实际问题中。在实际场景中，合理选择图的表示方法能够显著提升算法性能和代码的可维护性。