Python图的表示方法详解（邻接表与邻接矩阵实现指南）

什么是图？

图由顶点（Vertex/Node）和边（Edge）组成。例如，社交网络中的用户就是顶点，好友关系就是边。图可以是有向的（如关注关系）或无向的（如朋友关系）。

方法一：邻接矩阵（Adjacency Matrix）

邻接矩阵使用一个二维数组来表示图。如果顶点 i 和顶点 j 之间有边，则 matrix[i][j] = 1（或权重值），否则为 0。

优点：查询两个顶点是否相连非常快（O(1) 时间复杂度）
缺点：空间占用大，尤其当图很稀疏时（即边很少）

class GraphMatrix:    def __init__(self, num_vertices):        self.num_vertices = num_vertices        # 初始化一个全0的二维列表        self.matrix = [[0 for _ in range(num_vertices)]                        for _ in range(num_vertices)]        def add_edge(self, u, v, weight=1):        """添加一条从u到v的边，weight为权重（默认为1）"""        if 0 <= u < self.num_vertices and 0 <= v < self.num_vertices:            self.matrix[u][v] = weight            # 如果是无向图，还需添加反向边            # self.matrix[v][u] = weight        def print_matrix(self):        for row in self.matrix:            print(row)# 使用示例graph = GraphMatrix(4)graph.add_edge(0, 1)graph.add_edge(1, 2)graph.add_edge(2, 3)graph.print_matrix()

方法二：邻接表（Adjacency List）

邻接表使用一个列表（或字典）来存储每个顶点的邻居。这是更常用、更节省空间的方式，特别适合稀疏图。

优点：节省空间，遍历邻居高效
缺点：判断两顶点是否相连需要遍历（O(degree) 时间）

class GraphList:    def __init__(self):        self.graph = {}        def add_vertex(self, vertex):        if vertex not in self.graph:            self.graph[vertex] = []        def add_edge(self, u, v, weight=None):        """添加边，支持带权重（用于加权图）"""        if u not in self.graph:            self.add_vertex(u)        if v not in self.graph:            self.add_vertex(v)                # 无向图：双向添加        if weight is None:            self.graph[u].append(v)            self.graph[v].append(u)        else:            # 存储为 (邻居, 权重) 元组            self.graph[u].append((v, weight))            self.graph[v].append((u, weight))        def print_graph(self):        for vertex in self.graph:            print(f"{vertex}: {self.graph[vertex]}")# 使用示例graph = GraphList()graph.add_edge('A', 'B')graph.add_edge('B', 'C')graph.add_edge('C', 'D')graph.print_graph()

如何选择？

- 如果你的图是稠密图（边数接近顶点数的平方），使用邻接矩阵更合适。
- 如果是稀疏图（如社交网络、网页链接），强烈推荐使用邻接表，它能显著节省内存。

总结

通过本教程，你已经掌握了Python图的表示方法中最核心的两种技术：邻接矩阵和邻接表。无论你是要实现最短路径算法（如Dijkstra）、深度优先搜索（DFS）还是广度优先搜索（BFS），正确的图表示都是成功的第一步。

记住：没有绝对“最好”的方法，只有“更适合”你当前问题的方法。多练习、多尝试，你会越来越熟练！

关键词回顾：Python图的表示方法、邻接表、邻接矩阵、图数据结构。