视频字幕
拓扑排序是对有向无环图进行线性排序的算法。它广泛应用于课程安排、任务调度等场景。图中每个节点的入度表示有多少条边指向该节点。比如这个课程依赖图中，数学课的入度为0，表示它不依赖其他课程，而线代的入度为1，表示它依赖一门课程。
拓扑排序算法的基本步骤如下：首先计算所有节点的入度，然后找出入度为0的节点，将它们加入结果序列。接下来从图中删除这些节点及其所有出边，并更新相邻节点的入度。重复这个过程，直到处理完所有节点。这样就得到了一个拓扑排序的序列。
让我们通过具体例子来演示拓扑排序过程。首先计算所有节点的入度。数学课的入度为0，物理课的入度为1，化学课的入度为1，高数的入度为1，线代的入度为1。找到入度为0的节点是数学，将其加入结果序列。
删除数学节点及其所有出边后，更新剩余节点的入度。现在物理和高数的入度都变为0，化学和线代的入度仍为1。将物理和高数加入结果序列，得到数学、物理、高数。
继续这个过程，删除物理和高数节点后，化学和线代的入度变为0，最终得到拓扑排序序列：数学、物理、高数、化学、线代。拓扑排序算法的时间复杂度为O(V+E)，空间复杂度为O(V)，广泛应用于任务调度、依赖管理和编译顺序等场景。
入度计算是拓扑排序的第一步。我们需要遍历图中的所有边，对每条边从u到v，将节点v的入度加1。在这个例子中，节点A的入度为0，节点B的入度为1，节点C的入度为1，节点D的入度为1，节点E的入度为2，节点F的入度为2。入度反映了每个节点有多少个前驱节点，也就是需要满足多少个依赖条件。
删除零入度节点是拓扑排序的核心步骤。首先找到入度为0的节点，在这个例子中是节点A。将节点A加入结果序列，然后从图中删除节点A及其所有出边。删除节点A后，原本指向节点B和D的边也被删除，因此节点B和D的入度都会减1。这样我们就完成了第一轮的删除操作。
现在让我们完整演示拓扑排序算法的执行过程。初始状态下，只有节点A的入度为0。第一步删除A后，B和D的入度变为0。第二步删除B和D后，C的入度变为0。第三步删除C后，E的入度变为0。第四步删除E后，F的入度变为0。最后删除F，得到完整的拓扑排序序列：A、B、D、C、E、F。
拓扑排序算法的实现使用邻接表存储图，数组存储入度，队列存储零入度节点。算法首先计算所有节点的入度，然后将入度为0的节点加入队列。在主循环中，不断从队列中取出节点，加入结果序列，并更新其邻居节点的入度。时间复杂度为O(V+E)，其中V是节点数，E是边数。空间复杂度为O(V)。这个算法高效且实用，广泛应用于各种依赖关系的处理。