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

什么时候该把问题看成图

什么时候该把问题看成图

当题目里同时出现“对象之间存在关系”以及“要沿关系寻找、判断或优化”时,图模型通常值得优先考虑。本篇用一套可复用的识别方法,把自然语言中的对象、关系、路径和状态转移映射成可计算的图。

学习目标

  • 能从题目中识别顶点、边以及边的方向和权重。
  • 能区分路径、连通性与状态转移这几类典型图问题。
  • 能判断什么时候图模型反而会让问题变复杂。

先找图模型的四个信号

判断一个问题是否适合建图,不要先想“该用 BFS 还是 Dijkstra”,而要先看题目是否同时出现以下信号:有一组对象;对象之间存在成对关系;答案依赖关系链;需要判断可达、最短、顺序、环或连通结构。

例如“课程是否能按要求修完”中,课程是对象,先修依赖是关系;“从城市 A 到城市 B 的最低费用”中,城市是对象,交通线路是关系,费用可以作为边权。只要问题核心是沿关系传播或选择路径,图通常比数组或单纯集合更自然。

把自然语言映射为顶点和边

建图时先决定“什么是顶点”,再决定“什么关系值得变成边”。顶点应代表算法真正需要区分的实体或状态,边则代表一次允许的连接、依赖或转移。

从题意到图模型的映射关系

以“社交网络中两个人是否间接认识”为例,用户可以作为顶点,关注或好友关系作为边。如果关系有方向,如“甲关注乙”不代表“乙关注甲”,就使用有向边;如果关系天然对称,如双向好友,可以使用无向边。

权重只在关系本身带有代价时加入,例如距离、时间、价格或风险。没有代价时不要为了“看起来完整”随意给边加权,否则会把无权问题误导成加权最短路问题。

路径、连通与状态转移要分清

三类题目都可以建图,但顶点的含义不同。路径问题通常把现实对象作为顶点,例如城市、服务器或网页;连通性问题关注哪些对象属于同一连接区域;状态转移问题则把“当前局面”本身作为顶点。

例如密码锁从 0000 每次转动一位得到新状态,这时顶点不是“数字 0 到 9”,而是完整状态,如 0000、0001。一次合法操作就是一条边。建模粒度一旦错了,后续再正确的搜索算法也得不到正确答案。

如果一个状态由多个变量共同决定,就要确认是否需要把这些变量一起放入顶点。判断标准是:两个看起来相同的顶点,若未来可执行的动作或代价不同,它们就不能被合并为同一个状态。

什么时候不该用图

并不是出现“关系”就必须建图。若问题只需要一次排序、区间统计、频次聚合,关系不会被反复沿链访问,数组、哈希表或树结构通常更直接。

还要警惕状态空间爆炸。若把每种组合状态都建成顶点,顶点数可能呈指数增长。此时即使图模型在概念上正确,也要继续寻找压缩状态、剪枝、动态规划或隐式建图的方法。

真正有效的建图不是把题目画成很多点和线,而是找到最小但足够表达约束的顶点与边。一旦这个抽象完成,后续选择遍历、最短路、拓扑排序或连通性算法才有可靠基础。

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

目录与阅读设置

阅读设置

17

记录一个想法

什么时候该把问题看成图

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

登录哪都通