掌握图数据结构：Python图数据结构基础详解（从零开始构建图与遍历）

图的两种主要表示方法

在Python中，我们通常使用以下两种方式来表示图：

• 邻接矩阵（Adjacency Matrix）：使用二维数组表示节点之间的连接关系。
• 邻接表（Adjacency List）：使用字典或列表存储每个节点的邻居。

对于稀疏图（边远少于节点数平方），邻接表Python实现更节省空间，因此我们重点讲解邻接表。

用Python实现图（邻接表）

下面是一个简单的无向图类实现：

class Graph:    def __init__(self):        # 使用字典存储图，键是节点，值是邻居列表        self.graph = {}    def add_vertex(self, vertex):        """添加节点"""        if vertex not in self.graph:            self.graph[vertex] = []    def add_edge(self, vertex1, vertex2):        """添加无向边"""        # 确保两个节点都存在        self.add_vertex(vertex1)        self.add_vertex(vertex2)        # 添加双向连接        self.graph[vertex1].append(vertex2)        self.graph[vertex2].append(vertex1)    def print_graph(self):        """打印图的结构"""        for vertex in self.graph:            print(f"{vertex}: {self.graph[vertex]}")

使用示例：

# 创建图实例g = Graph()# 添加边g.add_edge('A', 'B')g.add_edge('A', 'C')g.add_edge('B', 'D')g.add_edge('C', 'D')g.print_graph()# 输出：# A: ['B', 'C']# B: ['A', 'D']# C: ['A', 'D']# D: ['B', 'C']

图的遍历：深度优先搜索（DFS）与广度优先搜索（BFS）

遍历是图操作的核心。图遍历算法主要有两种：

• 深度优先搜索（DFS）：沿着一条路径尽可能深入，再回溯。
• 广度优先搜索（BFS）：一层一层地访问邻居节点。

我们在上面的 Graph 类中添加 DFS 和 BFS 方法：

from collections import dequeclass Graph:    # ...（前面的代码保持不变）...    def dfs(self, start, visited=None):        """深度优先搜索"""        if visited is None:            visited = set()        visited.add(start)        print(start, end=' ')                for neighbor in self.graph.get(start, []):            if neighbor not in visited:                self.dfs(neighbor, visited)    def bfs(self, start):        """广度优先搜索"""        visited = set()        queue = deque([start])        visited.add(start)                while queue:            vertex = queue.popleft()            print(vertex, end=' ')                        for neighbor in self.graph.get(vertex, []):                if neighbor not in visited:                    visited.add(neighbor)                    queue.append(neighbor)

测试遍历：

g = Graph()g.add_edge('A', 'B')g.add_edge('A', 'C')g.add_edge('B', 'D')g.add_edge('C', 'D')print("DFS:", end=' ')g.dfs('A')  # 可能输出：A B D Cprint("\nBFS:", end=' ')g.bfs('A')  # 可能输出：A B C D

总结

通过本教程，你已经掌握了Python图数据结构的基础知识，包括图的表示（特别是邻接表Python实现）、构建以及两种核心的图遍历算法（DFS 和 BFS）。这些是解决更复杂图问题（如最短路径、连通分量等）的基石。

建议你动手敲一遍代码，修改节点和边，观察输出结果，加深理解。后续可以探索有向图、带权图以及 Dijkstra、Floyd 等高级算法。

记住，掌握图的表示方法是迈向图算法高手的第一步！