Python邻接表详解（小白也能学会的图数据结构表示法）

为什么使用Python实现邻接表？

Python语言简洁易读，内置的数据结构（如字典和列表）非常适合用来构建邻接表。通过使用Python邻接表，你可以快速搭建图模型，进行深度优先搜索（DFS）、广度优先搜索（BFS）等图算法的实验。

邻接表的基本结构

假设我们有一个无向图，包含顶点 A、B、C、D，边为 A-B、A-C、B-D。其邻接表可表示为：

{    'A': ['B', 'C'],    'B': ['A', 'D'],    'C': ['A'],    'D': ['B']}

每个顶点作为字典的键，其值是一个列表，包含所有与该顶点直接相连的邻居顶点。

用Python实现邻接表

下面我们编写一个简单的 Graph 类，支持添加顶点、添加边，并打印整个邻接表。

class Graph:    def __init__(self):        # 使用字典存储邻接表        self.adj_list = {}    def add_vertex(self, vertex):        """添加一个顶点"""        if vertex not in self.adj_list:            self.adj_list[vertex] = []    def add_edge(self, v1, v2):        """添加一条无向边"""        # 确保两个顶点都存在        if v1 not in self.adj_list:            self.add_vertex(v1)        if v2 not in self.adj_list:            self.add_vertex(v2)                # 无向图：双向连接        self.adj_list[v1].append(v2)        self.adj_list[v2].append(v1)    def print_graph(self):        """打印邻接表"""        for vertex in self.adj_list:            print(f"{vertex}: {self.adj_list[vertex]}")# 使用示例graph = Graph()graph.add_edge('A', 'B')graph.add_edge('A', 'C')graph.add_edge('B', 'D')graph.print_graph()# 输出：# A: ['B', 'C']# B: ['A', 'D']# C: ['A']# D: ['B']

扩展：有向图的邻接表

如果是有向图，只需在 add_edge 方法中只添加单向连接即可：

def add_directed_edge(self, from_v, to_v):    if from_v not in self.adj_list:        self.add_vertex(from_v)    if to_v not in self.adj_list:        self.add_vertex(to_v)        # 有向图：只从 from_v 指向 to_v    self.adj_list[from_v].append(to_v)

总结

通过本教程，你已经掌握了如何用Python语言实现图的邻接表表示。邻接表不仅节省内存，而且便于遍历邻居节点，是学习图算法的基础。无论你是准备面试，还是开发实际项目，掌握邻接表实现教程中的这些技巧都将大有裨益。

记住，实践是最好的老师！尝试自己构建更复杂的图，比如加入权重、实现图的遍历算法，你会对Python图数据结构有更深的理解。