有向无环图 DAG

数据结构

所属模块：DS-4 图 · 本模块第 6 / 14 个概念

在「DS-4 图」概念体系中的位置

flowchart TD
    A["多对多的任意关系"] --> B["存储：邻接矩阵（稠密）<br/>vs 邻接表（稀疏）"]
    B --> C["遍历：DFS（栈）/ BFS（队列）<br/>+ visited 防环"]
    C --> D["最小生成树 MST<br/>Prim（选点）/ Kruskal（选边）"]
    C --> E["最短路径<br/>Dijkstra（单源非负）/ Floyd（全源）/ BFS（无权）"]
    A --> F["有向无环图 DAG"]
    F --> G["AOV：拓扑排序<br/>事件先后顺序"]
    F --> H["AOE：关键路径<br/>最长路径 = 最短工期"]

核心概念：

概念	要点	易考点
度/入度/出度	无向图： $\sum$ 度 $= 2e$ ；有向图： $\sum$ 入度 $=\sum$ 出度 $= e$	由邻接矩阵求度：无向图数行（或列）的 1；有向图度 = 行（出）+ 列（入）（2013-7）
连通/强连通	无向连通图至少 $n-1$ 条边；完全图 $n(n-1)/2$ 条	2009-7（连通图性质辨析）
邻接矩阵 $A^m$	$A^m$ 的非零元 $(i,j)$ 表示 i 到 j 长度为 m 的路径条数	2015-42 大题直接考
生成树	含全部 $n$ 顶点、 $n-1$ 条边的极小连通子图	MST 代价唯一、形状未必唯一（2012-8、2017-42）
AOV 网	顶点 = 活动，弧 = 先后关系；有环则无拓扑序列	2011-8 III（有拓扑序列 ⟹ 无回路）
AOE 网	顶点 = 事件，边 = 活动（带权）；关键路径 = 源到汇的最长路径	2020-8：缩短任一关键活动不一定缩短工期（有多条关键路径时），经典陷阱