15.082 和 6.855J拓扑排序拓扑排序基础定理. 如果每个结点至少有一条出弧，那么深度优先搜索的第一条不可进入的弧确定一有向圈. 推论 1. 如果 G 没有有向圈，那么在 G 中存在没有出弧的结点。且在 G 中至少有一结点没有入弧.推论 2. 如果 G 没有有向圈，那么可以重标号结点，以至于对每条弧 (i,j) 有i j. 1 4 6 7 32初始化1245 3678 next01 2 3 4 5 6 7 82 2 3 2 1 1 0 2判定每个结点的入度LIST 是 入度为 0 的结点的集合.“Next” 将是在拓次序的结点的标号.LIST7结点入度3从LIST 选择一结点 next01 2 3 4 5 7 82 2 3 2 1 0 2从 LIST 选择一结点，并删除它.LIST7next := next +1order(i) := next;更新入度更新 LIST111245 367870 1561结点入度4从LIST 选择一结点 next01 2 3 5 7 82 2 3 1 1 0 2从 LIST 选择一结点，并删除它.LIST7next := next +1order
