Python如何构建带有默认权重的有向图_利用dict嵌套dict实现-Python教程-PHP中文网

可行，且在小到中等规模图（顶点数≤10⁴、边数≤10⁵）、无需频繁运行拓扑/最短路算法时，比networkx更快更可控；但查边、删边、遍历需谨慎处理keyerror和空字典。

python如何构建带有默认权重的有向图_利用dict嵌套dict实现

用 `dict` 嵌套 `dict` 表示带默认权重的有向图，本质是邻接表的轻量实现

直接说结论：可行，且在小到中等规模图（顶点数 ≤ 10⁴，边数 ≤ 10⁵）、无需频繁拓扑/最短路算法的场景下，比 networkx 更快、更可控。核心思路是外层 dict 键为起点，值为内层 dict，其键为目标点，值为边权重。

不推荐把它当通用图结构反复调用 Dijkstra 或 Floyd —— 缺少边存在性检查、无统一权重默认值接口、更新成本高，容易写出 KeyError 或逻辑错漏。

初始化时如何安全设置默认权重

常见错误是直接写 graph = {u: {v: 1.0}}，但后续新增边时忘记设权，或误用 .setdefault(u, {})[v] = weight 却没处理 u 不存在的情况。

testing-python

使用pytest编写和评估有效的Python测试。适用于编写测试、审查测试代码、调试测试失败或提高测试覆盖率。

下载

推荐用 graph.setdefault(u, {})[v] = weight，它自动创建空 dict 并赋值，避免 KeyError

若所有边初始都应为同一默认值（如 1.0），可封装函数：

def add_edge(graph, u, v, weight=1.0):
    graph.setdefault(u, {})[v] = weight

注意：graph.get(u, {}).get(v) 返回 None 而非默认权重；要返回默认值，得写 graph.get(u, {}).get(v, 1.0) —— 每次访问都得显式传默认值，易遗漏

查边、遍历、删边时的典型陷阱

这类结构对“查是否存在边”和“删边”不够友好，稍不注意就出错。

查边存在性不能只写 v in graph[u]，必须先确认 u in graph，否则抛 KeyError；稳妥写法是 u in graph and v in graph[u]
获取权重推荐用 graph.get(u, {}).get(v, 1.0)，而不是 graph[u][v]（后者失败即崩）
删边要分两步：先删内层键 graph[u].pop(v, None)，再判断是否需清理空节点 if not graph[u]: del graph[u]，否则残留空 dict 影响后续逻辑

遍历所有边建议用嵌套循环：

for u in graph:
    for v, w in graph[u].items():
        print(u, '->', v, 'weight:', w)

什么时候该换用其他结构

当出现以下任一情况，说明 dict 嵌套已到维护临界点：

需要频繁查询「某点入度」或「所有指向 u 的节点」——当前结构只存出边，反向查得遍历全部键值对
权重类型复杂（如 tuple、custom object），或需支持边属性扩展（如容量、时间戳）——嵌套 dict 很快变成 {u: {v: {'weight': 1.0, 'cap': 10}}}，失去简洁性
要跑标准图算法（如 heapq 实现的 Dijkstra）——每次取邻居都要 graph.get(u, {})，代码冗长且易漏，默认权重逻辑分散各处
顶点名不是字符串/数字（比如是自定义对象），而你又忘了重载 __hash__ —— dict 键会报错

真要扩展，不如早期就用 defaultdict(lambda: defaultdict(lambda: 1.0))，或直接上 networkx.DiGraph 配 add_edge(u, v, weight=...) 和 get_edge_data(u, v, default=...)。