- 顺序问题
  - 穿衣服的顺序
    - 里面先穿，外面后穿
    - 上衣和裤子顺序不限
  - 计算机课程学习顺序
    - 高等数学与计算机导论在第一学期
    - 离散数学与程序设计语言在第二学期
    - 数据结构在第三学期
    - 数据结构依赖离散数学与程序设计语言
- 子工程依赖关系
  - 大学学习看作工程
  - 每门课程是子工程
  - 子工程需遵循顺序
- 拓扑排序方法
  - 抽象为有向图
    - 顶点表示课程活动
    - 弧表示先修关系
  - AOV网
    - 用顶点表示活动的有向图
    - 拓扑排序生成线性序列
  - 检测有向图中的环
    - 图中存在环则无法拓扑排序
    - 拓扑序列包含所有顶点说明无环
- 拓扑排序步骤
  - 选择没有前驱的顶点输出
  - 删除该顶点及从其出发的弧
  - 重复上述步骤直至图为空
  - 若最后图不为空且无前驱顶点，则存在环
- 实例分析
  - 初始无前驱顶点为C1和C2
  - 输出C2并删除相关弧
  - 输出C1并删除相关弧
  - 继续输出C4、C6、C3、C5、C7
- 拓扑排序特性
  - 序列不唯一
  - 可采用队列存储待输出顶点
- 图的存储方式
  - 邻接矩阵
    - 元素为1表示有弧，为0表示无弧
  - 邻接表
    - 数组存储顶点信息
    - 单链表存储从顶点出发的弧
- 改进邻接表
  - 增加入度域
  - 统计顶点入度
  - 使用堆栈暂存入度为0的顶点
- 拓扑排序实现过程
  - 邻接表存储结构
  - 输入弧时统计入度
  - 初始入度为0的顶点入栈
  - 出栈输出顶点并修改弧头顶点入度
  - 入度为0的顶点入栈
  - 重复直至堆栈为空
- 检测环的存在
  - 若堆栈为空但未包含所有顶点，则存在环
- 代码实现要点
  - 堆栈存储顶点
  - 扫描弧链表修改入度
  - 修改后入度为0的顶点入栈
- 思考题
  - 如何通过子工程缩短工期