Python邻接多重表详解（手把手教你用Python实现图的邻接多重表存储结构）

邻接多重表的数据结构设计

我们需要定义两种节点：

• 顶点节点（VertexNode）：包含顶点信息和指向第一条关联边的指针。
• 边节点（EdgeNode）：包含两个顶点的索引、边的信息（如权重）、访问标记，以及分别指向两个顶点的下一条边的指针。

Python代码实现

下面我们将用Python类来实现邻接多重表。为了便于理解，我们不使用复杂的指针，而是用列表和对象引用来模拟。

class EdgeNode:    def __init__(self, ivex, jvex, weight=1):        self.ivex = ivex      # 顶点i的索引        self.jvex = jvex      # 顶点j的索引        self.weight = weight  # 边的权重（可选）        self.marked = False   # 是否被访问过        self.ilink = None     # 指向顶点i的下一条边        self.jlink = None     # 指向顶点j的下一条边class VertexNode:    def __init__(self, data):        self.data = data      # 顶点数据（如名称）        self.first_edge = None  # 指向第一条关联边class AdjacencyMultilist:    def __init__(self):        self.vertices = []    # 顶点列表    def add_vertex(self, data):        """添加顶点"""        self.vertices.append(VertexNode(data))    def add_edge(self, i, j, weight=1):        """添加无向边 (i, j)"""        if i >= len(self.vertices) or j >= len(self.vertices):            raise IndexError("顶点索引超出范围")                edge = EdgeNode(i, j, weight)                # 将新边插入到顶点i的边链表头部        edge.ilink = self.vertices[i].first_edge        self.vertices[i].first_edge = edge                # 将新边插入到顶点j的边链表头部        edge.jlink = self.vertices[j].first_edge        self.vertices[j].first_edge = edge    def display(self):        """打印邻接多重表结构"""        for idx, vertex in enumerate(self.vertices):            print(f"顶点 {vertex.data} 的边:")            edge = vertex.first_edge            while edge:                other = edge.jvex if edge.ivex == idx else edge.ivex                print(f"  -> 连接到 {self.vertices[other].data}, 权重={edge.weight}")                # 根据当前顶点选择正确的link                edge = edge.ilink if edge.ivex == idx else edge.jlink

使用示例

现在我们创建一个简单的无向图并测试我们的实现：

# 创建图graph = AdjacencyMultilist()# 添加4个顶点for v in ['A', 'B', 'C', 'D']:    graph.add_vertex(v)# 添加边graph.add_edge(0, 1)  # A-Bgraph.add_edge(0, 2)  # A-Cgraph.add_edge(1, 2)  # B-Cgraph.add_edge(2, 3)  # C-D# 显示图结构graph.display()

运行结果将显示每个顶点连接的所有边，清晰地反映出图的结构。

为什么选择邻接多重表？

相比邻接矩阵和邻接表，邻接多重表在处理无向图时具有以下优势：

• 节省空间：每条边只存储一次。
• 便于操作：可以轻松标记边是否被访问，适用于图遍历算法（如深度优先搜索）。
• 结构清晰：边与两个顶点直接关联，逻辑直观。

总结

通过本教程，你已经学会了如何用Python语言实现邻接多重表这一重要的图的存储结构。无论你是初学者还是有一定基础的学习者，掌握这种结构都将帮助你在解决图论问题时更加得心应手。希望这篇数据结构教程对你有所帮助！

关键词回顾：Python邻接多重表、图的存储结构、邻接多重表实现、数据结构教程。