数据结构与算法 / 系统课时

权重和多重边怎么建模

权重和多重边怎么建模

真实图问题里的边往往不只有“连不连接”这一项信息,还可能带距离、费用、容量,并出现自环或同一对节点之间的多条边。稳定的建模方式应把边当成独立记录,而不是只保存一个邻接关系。

学习目标

  • 判断什么时候需要在边上保存权重或其他属性
  • 正确处理自环和同一对节点之间的多重边
  • 根据后续算法需求选择不会丢失信息的输入结构

权重表示通过一条边的代价

无权图只关心边是否存在,很多问题可以把每条边看成相同代价。带权图则需要为边保存额外数值,例如距离、时间、价格、容量或收益。

权重的含义必须跟题目目标保持一致。道路长度可以作为距离,网络链路延迟可以作为时间,但二者不能因为都写成数字就混为一种指标。后续算法实际上是在这些权重定义之上进行比较和累积。

例如最短路中的“最短”并不一定指几何距离。如果边权代表费用,算法求出的就是最低费用路径;如果边权代表时间,结果就是最短耗时路径。

多重边不能随意覆盖

多重边指同一对节点之间同时存在两条或更多边。例如城市 A 到城市 B 可能有多班不同价格和耗时的航班,两台网络设备之间也可能存在多条独立链路。

如果建图时只用“起点加终点”作为唯一键,并让后读入的边覆盖先读入的边,就会丢失信息。是否允许合并多重边,要看后续问题需要什么。

若任务只关心两点间最小费用,可以在明确证明安全后,只保留最小权重边;如果还需要统计方案数、区分线路编号或处理不同容量,就必须保留每一条边。

带权边、自环与多重边的结构关系

自环是一条真实存在的边

自环是起点和终点相同的边,例如 A→A。它看起来没有把两个不同节点连接起来,但在一些问题中仍会影响度数、环判断、状态转移或路径计数,因此不能在读入阶段默认删除。

是否保留自环,同样取决于任务语义。如果问题明确只研究不同节点之间的移动,自环可能无效;如果边代表状态转移、交易或依赖,自环本身可能就是需要检测的异常或合法行为。

边属性应跟着边保存

当边除了权重还包含编号、类型、容量或启用状态时,最好把这些信息组织成一条完整的边记录。邻接表中的每个元素不再只是“邻居是谁”,而是“通过哪条边能到哪个节点,以及这条边具有什么属性”。

这种结构尤其适合多重边,因为两条端点相同的边仍然可以拥有不同的编号和属性。相比只维护一个二维权重表,它更不容易在扩展需求时丢失信息。

选择输入结构时可以先问后续算法需要访问什么:只判断是否相邻,可以保存布尔关系;需要遍历稀疏图和读取边权,邻接表更自然;需要枚举所有原始边进行松弛或排序时,还应保留独立的边列表。

合并边之前先证明不会改变答案

为了节省空间而合并多重边并不是错误,但它必须是算法层面的有意识优化。例如求非负权最短路时,同方向的两条平行边若只差权重,较大权重边通常不会形成更短路径,因此可在特定条件下舍弃。

但如果问题涉及边数、方案数、容量、边编号或逐条删除操作,同样的合并就可能改变答案。稳定建模的原则是先完整表达原始关系,再根据题目目标做有依据的压缩,而不是在输入阶段凭直觉删边。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

权重和多重边怎么建模

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通