有向图 vs 无向图
核心区别
| 维度 |
有向图 |
无向图 |
| 边方向 |
有方向（有序对 (u,v)） |
无方向（无序对 {u,v}） |
| 度区分 |
区分入度/出度 |
不区分（度=入度+出度） |
| 连通概念 |
强连通图/弱连通图 |
连通图 |
| 最短路径 |
需考虑方向（Dijkstra适用） |
无方向限制（BFS即最短路径） |
| 常见应用 |
流程调度、依赖关系、状态机 |
社交网络、道路网络（无单行道） |
详细对比
边与度
- 有向图：边 (u→v) 与 (v→u) 是不同边；节点度 = 入度 + 出度
- 无向图：边 {u,v} 与 {v,u} 是同一条边；节点度 = 连接的边数
连通性
| 概念 |
有向图 |
无向图 |
| 基础连通 |
强连通图（互为可达） |
连通图（任意两节点有路径） |
| 分量 |
强连通分量 |
连通分量 |
| 忽略方向的连通 |
弱连通图 |
本身即连通图 |
算法适配
| 算法 |
有向图 |
无向图 |
| BFS/DFS遍历 |
✅ 支持 |
✅ 支持 |
| 最短路径（Dijkstra） |
✅ 支持 |
✅ 支持（BFS更简单） |
| 拓扑排序 |
✅ 仅适用（依赖入度） |
❌ 不适用 |
| 欧拉回路 |
需满足入度=出度 |
需满足0或2个奇数度节点 |
应用场景对比
| 场景 |
有向图 |
无向图 |
| 社交网络（关注关系） |
✅（A关注B≠B关注A） |
✅（好友关系） |
| 道路网络 |
✅（单行道） |
✅（双行道） |
| 任务依赖（A→B需先完成A） |
✅ |
❌ |
| 分子结构（化学键无方向） |
❌ |
✅ |
相关概念
- 有向图：有向图详细概念页
- 无向图：无向图详细概念页
- 图：图的基础概念
- 度：节点度的概念
- 入度：有向图入度
- 出度：有向图出度