Python图结构实现：邻接表、加权字典与邻接矩阵详解

本文通过具体实例，详细解析Python中数据结构与算法的核心组件——图结构（Graph），旨在为读者提供清晰的实现思路与代码参考。

图结构是算法领域中最具表现力的框架之一。值得注意的是，树结构仅仅是图结构的一种特殊子集形式。

若能将实际问题抽象为图问题，通常意味着该问题已接近可解状态；而若能进一步利用树结构对问题进行建模，则往往意味着已经找到了高效且有效的解决方案。

邻接表及加权邻接字典

实现图结构最直观的方式之一是采用邻接列表。其核心逻辑是为每个节点维护一个独立的邻接列表。以下实现假设存在 n 个节点，编号范围从 0 至 n-1。

虽然节点可以是任意对象并赋予特定标签，但使用 0 到 n-1 区间内的整数作为节点标识能显著简化实现。因为数字索引在访问效率上远高于其他类型，从而提升了整体操作的便捷性。

每个邻接列表本质上是一个数字序列，我们可以将这些序列整合到一个大小为 n 的主列表中，并通过节点编号进行索引访问。尽管列表内节点的顺序并无特定要求，但从数据结构角度看，这实际上实现了邻接集（adjacency sets）的功能。此处沿用“列表”这一术语主要出于历史习惯，实际上Python提供了更专用的 set 类型。

参考下图，我们可以直观理解图结构的多种表示方式。在处理图相关任务时，需遵循一个核心原则：图的最佳表示形式取决于具体的应用场景和操作需求。

a, b, c, d, e, f, g, h = range(8)
N = [
  {b, c, d, e, f},
  {c, e},
  {d},
  {e},
  {f},
  {c, g, h},
  {f, h},
  {f, g}
]

在图论定义中，N(v) 表示节点 v 的所有邻居节点构成的集合。

>>> b in N[a]         # neighborhood membership
True
>>> len(N[f])         # out-degree：出度
3

加权邻接字典

使用 dict 类型替代 set 或 list 来表示邻接关系。在字典结构中，每个邻居节点对应一个键值对，其中额外的值用于存储与该邻居节点（或出边）相关的属性，例如边的权重信息。

a, b, c, d, e, f, g, h = range(8)
N = [
  {b:2, c:1, d:3, e:9, f:4},
  {c:4, e:4},
  {d:8},
  {e:7},
  {f:5},
  {c:2, g:2, h:2},
  {f:1, h:6},
  {f:9, g:8}
]

以下是客户端调用该结构的示例代码。

>>> b in N[a]         # neighborhood membership
True
>>> len(N[f])         # out-degree
3
>>> N[a][b]          # Edge weight for (a, b)
2

邻接矩阵

邻接矩阵是图的另一种常见表示法，其显著区别在于它不直接列出每个节点的具体邻居，而是通过矩阵位置隐含节点间的连接关系。

a, b, c, d, e, f, g, h = range(8)
N =[
  [0, 1, 1, 1, 1, 1, 0, 0],
  [0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 1, 0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0, 1, 0, 1],
  [0, 0, 0, 0, 0, 1, 1, 0],
]

关于邻接矩阵的关键特性说明如下：

（1）主对角线上的元素表示节点到自身的连接，值通常为0； （2）矩阵中每一行的元素之和等于该节点的出度； （3）矩阵中每一列的元素之和等于该节点的入度。

如需进一步了解Python相关知识，建议查阅本站系列教程，包括《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》以及《Python文件与目录操作技巧汇总》。

期望上述内容能对您的Python程序设计工作有所帮助。