Python链式前向星详解（小白也能学会的图存储结构实现）

Python 实现步骤

我们将逐步构建一个完整的链式前向星类，并演示如何添加边和遍历邻接点。

1. 初始化数据结构

首先，我们需要确定图的最大节点数和最大边数，然后初始化三个核心数组。

class ChainForwardStar:    def __init__(self, n, m):        """        n: 节点数量（节点编号通常从 1 到 n）        m: 边的数量上限        """        self.n = n        self.m = m        self.head = [-1] * (n + 1)  # head[u] 表示从 u 出发的第一条边的索引        self.to = [0] * (m + 1)     # to[i] 表示第 i 条边的终点        self.nxt = [0] * (m + 1)    # nxt[i] 表示与第 i 条边同起点的下一条边索引        self.edge_cnt = 0           # 当前边的计数器  

2. 添加边的方法

每次添加一条从 u 到 v 的边时，我们将其插入到链表头部（头插法），这样可以保证后续遍历时顺序与输入相反（但不影响正确性）。

    def add_edge(self, u, v):        """        添加一条从 u 到 v 的有向边        """        self.edge_cnt += 1        self.to[self.edge_cnt] = v        self.nxt[self.edge_cnt] = self.head[u]        self.head[u] = self.edge_cnt  

3. 遍历某个节点的所有出边

要遍历从节点 u 出发的所有边，只需从 head[u] 开始，沿着 nxt 数组跳转，直到值为 -1。

    def get_neighbors(self, u):        """        返回节点 u 的所有邻接点（出边终点）        """        neighbors = []        i = self.head[u]        while i != -1:            neighbors.append(self.to[i])            i = self.nxt[i]        return neighbors  

完整示例：构建并查询图

下面是一个完整的使用示例，展示如何用 Python链式前向星 构建一个简单有向图并查询邻接点。

# 创建一个最多 5 个节点、10 条边的图graph = ChainForwardStar(n=5, m=10)# 添加边：1→2, 1→3, 2→4, 3→4, 4→5graph.add_edge(1, 2)graph.add_edge(1, 3)graph.add_edge(2, 4)graph.add_edge(3, 4)graph.add_edge(4, 5)# 查询节点 1 的邻居print("节点 1 的邻居：", graph.get_neighbors(1))  # 输出: [3, 2]# 查询节点 4 的邻居print("节点 4 的邻居：", graph.get_neighbors(4))  # 输出: [5]  

为什么选择链式前向星？

相比 Python 中常用的 defaultdict(list) 邻接表，链式前向星 具有以下优势：

• 内存连续，缓存友好，访问速度更快
• 无需动态扩容，避免了 list 的 append 开销
• 在已知边数上限的情况下，空间使用更可控

虽然在 Python 中这种优势不如 C++ 明显，但在处理大规模图数据或参加算法竞赛时，掌握 Python图算法 中的链式前向星实现仍然非常有价值。

总结

本文详细讲解了 链式前向星实现 的原理和 Python 代码，包括初始化、加边、遍历三个核心操作。即使你是算法小白，只要理解了三个数组的作用，就能轻松掌握这一高效的 图的存储结构。

建议你动手敲一遍代码，尝试构建自己的图，加深理解。掌握这一结构后，你将能更高效地实现 DFS、BFS、Dijkstra 等经典图算法！