Python实现十字链表存储图结构（小白也能看懂的图存储与稀疏矩阵高效表示教程）

十字链表的核心组件

要实现十字链表，我们需要定义两类节点：

• 顶点节点（VertexNode）：存储顶点信息，包含两个指针：first_in（第一条入边）和first_out（第一条出边）。
• 边节点（EdgeNode）：存储一条有向边的信息，包括：tail_vex（起点索引）、head_vex（终点索引）、h_link（指向同一终点的下一条边）、t_link（指向同一起点的下一条边）。

Python代码实现

下面是一个完整的十字链表实现，包含添加顶点、添加边和打印图结构的功能。

class EdgeNode:    def __init__(self, tail_vex, head_vex):        self.tail_vex = tail_vex   # 起点顶点索引        self.head_vex = head_vex   # 终点顶点索引        self.h_link = None         # 指向同一终点的下一条边（入边链）        self.t_link = None         # 指向同一起点的下一条边（出边链）class VertexNode:    def __init__(self, data):        self.data = data           # 顶点数据（如 'A', 'B'）        self.first_in = None       # 第一条入边        self.first_out = None      # 第一条出边class OrthogonalListGraph:    def __init__(self):        self.vertex_list = []      # 顶点列表        self.vertex_map = {}       # 顶点名到索引的映射    def add_vertex(self, vertex_data):        """添加顶点"""        if vertex_data not in self.vertex_map:            index = len(self.vertex_list)            self.vertex_map[vertex_data] = index            self.vertex_list.append(VertexNode(vertex_data))    def add_edge(self, start, end):        """添加有向边 start -> end"""        if start not in self.vertex_map or end not in self.vertex_map:            raise ValueError("顶点不存在，请先添加顶点")        tail_idx = self.vertex_map[start]        head_idx = self.vertex_map[end]        new_edge = EdgeNode(tail_idx, head_idx)        # 插入到出边链表（起点的 first_out）        new_edge.t_link = self.vertex_list[tail_idx].first_out        self.vertex_list[tail_idx].first_out = new_edge        # 插入到入边链表（终点的 first_in）        new_edge.h_link = self.vertex_list[head_idx].first_in        self.vertex_list[head_idx].first_in = new_edge    def print_graph(self):        """打印图结构"""        for i, v in enumerate(self.vertex_list):            print(f"顶点 {v.data} (索引{i}):")                        # 打印出边            out_edges = []            edge = v.first_out            while edge:                out_edges.append(self.vertex_list[edge.head_vex].data)                edge = edge.t_link            print(f"  出边: {' -> '.join(out_edges) if out_edges else '无'}")            # 打印入边            in_edges = []            edge = v.first_in            while edge:                in_edges.append(self.vertex_list[edge.tail_vex].data)                edge = edge.h_link            print(f"  入边: {' <- '.join(in_edges) if in_edges else '无'}")            print()

使用示例

现在我们用上面的类来构建一个简单的有向图：

# 创建图实例g = OrthogonalListGraph()# 添加顶点g.add_vertex('A')g.add_vertex('B')g.add_vertex('C')g.add_vertex('D')# 添加有向边g.add_edge('A', 'B')g.add_edge('A', 'C')g.add_edge('B', 'C')g.add_edge('C', 'D')g.add_edge('D', 'A')# 打印图结构g.print_graph()

输出结果如下：

顶点 A (索引0):  出边: B -> C  入边: D顶点 B (索引1):  出边: C  入边: A顶点 C (索引2):  出边: D  入边: A <- B顶点 D (索引3):  出边: A  入边: C

为什么选择十字链表？

十字链表在处理稀疏矩阵存储和有向图时具有显著优势：

• 空间效率高：只存储存在的边，避免邻接矩阵的大量零值浪费。
• 双向查询快：既能快速找到某顶点的所有出边，也能快速找到所有入边。
• 适合动态图：插入/删除边的时间复杂度较低。

总结

通过本教程，你已经掌握了如何用Python十字链表来高效存储有向图。这种结构不仅节省内存，还便于图算法的实现（如拓扑排序、强连通分量等）。无论你是学习Python数据结构教程的新手，还是需要优化图存储方案的开发者，十字链表都是一个值得掌握的重要工具。

记住，理解图的存储结构是深入图论和算法设计的第一步。动手实践上面的代码，你会对十字链表有更直观的认识！