数据结构与算法 / 系统课时
有向图和无向图差在哪
有向图和无向图差在哪
同一组节点,只要边是否带方向不同,可达性、度数定义和遍历结果就可能完全变化。建图前先判断关系能不能反向成立,才能避免把后续最短路、拓扑排序或连通性判断建立在错误模型上。
学习目标
- 根据题目中的关系判断应使用有向图还是无向图
- 理解方向对可达性、度数和遍历范围的影响
- 识别把单向关系误建成双向关系带来的典型错误
先判断关系能不能反向
无向图表示一种天然对称的关系:如果 A 与 B 相连,那么从 A 到 B 和从 B 到 A 都存在同一条连接。例如道路明确允许双向通行、两台设备建立对等连接,都适合抽象成无向边。
有向图表示关系具有起点和终点。关注、依赖、先修、任务调用等关系通常不能自动反向:A 依赖 B,并不意味着 B 也依赖 A。建模时应保留这种方向,否则原问题的约束会被改变。

方向首先改变可达性
在无向图中,只要 A 与 B 位于同一个连通分量,就能沿边从其中一个走到另一个。路径经过哪些节点可能不同,但边本身不会阻止反向移动。
有向图则必须逐条遵守箭头方向。即使 A 能到达 B,B 也未必能回到 A。因此描述有向图时,不能只问两个点是否相连,还要明确问“从谁能到谁”。
例如存在 A→B 和 B→C 时,从 A 可以到达 C;但没有额外的反向边时,从 C 无法沿原边回到 A。这也是强连通、拓扑排序等概念只在有向关系中具有特殊意义的原因。
度数的定义也不同
无向图中,一个节点的度数就是与它相接的边数。一条普通无向边会让两个端点的度数各增加 1。
有向图需要区分入度和出度。指向节点的边计入入度,从节点指出的边计入出度。比如 A→B 会让 A 的出度增加 1,同时让 B 的入度增加 1。
这个区别会直接影响算法条件。判断无向图的欧拉路径时会关注奇数度节点数量;拓扑排序则不断寻找入度为 0 的节点。把两套“度”混在一起,算法即使能运行,判断依据也已经错误。
遍历代码相似,建图方式不同
DFS 和 BFS 的基本遍历过程并不会因为图有方向就完全改变,真正决定能走到哪里的,是邻接关系中保存了哪些边。
如果输入给出一条无向边 A-B,邻接结构通常需要同时记录 A 到 B 和 B 到 A。若输入是一条有向边 A→B,则只记录 A 到 B;除非题目明确还存在 B→A,否则不能自行补上一条反向边。
建模时用三个问题检查方向
拿到题目后,可以依次检查:关系反过来是否仍然成立;从终点是否允许沿同一条边返回起点;题目是否出现入度、出度、依赖顺序、单向可达等方向性条件。只要任一关键约束依赖方向,就应优先按有向图建模。
方向不是边上的装饰信息,而是图本身的一部分。先把方向建对,后续的遍历、连通性和算法选择才有可靠基础。