LeetCode 拓扑排序 刷题模板
💡
原文中文，约4900字，阅读约需12分钟。
📝
内容提要
拓扑排序是一种对有向无环图（DAG）进行排序的算法，主要用于根据任务依赖关系调度任务。该算法通过删除入度为0的节点并更新相邻节点的入度，直到所有节点被访问。常见应用包括课程安排问题，判断是否可以完成所有课程学习。
🎯
关键要点
- 拓扑排序是一种对有向无环图（DAG）进行排序的算法，主要用于根据任务依赖关系调度任务。
- 拓扑排序的基本算法思想是通过不断删除入度为0的节点，并更新其相邻节点的入度，直到所有节点都访问过。
- 入度为0的节点是指没有任何边指向该节点的节点，可以直接访问。
- 拓扑排序的步骤包括初始化邻接表、将入度为0的节点加入队列、循环处理队列中的节点并更新相邻节点的入度。
- 拓扑排序的典型应用包括课程安排问题，判断是否可以完成所有课程学习。
- 在课程表问题中，给定课程的先修关系，判断是否可以完成所有课程的学习。
- 课程表 II 问题要求返回学习所有课程的顺序，如果不可能完成所有课程，则返回空数组。
❓
延伸问答
什么是拓扑排序？
拓扑排序是一种对有向无环图（DAG）进行排序的算法，用于根据任务依赖关系调度任务。
拓扑排序的基本算法步骤是什么？
拓扑排序的步骤包括初始化邻接表、将入度为0的节点加入队列、循环处理队列中的节点并更新相邻节点的入度，直到所有节点都访问过。
拓扑排序的入度为0的节点是什么意思？
入度为0的节点是指没有任何边指向该节点的节点，可以直接访问。
拓扑排序有哪些典型应用？
拓扑排序的典型应用包括课程安排问题，判断是否可以完成所有课程学习。
如何判断是否可以完成所有课程的学习？
可以通过拓扑排序判断，如果存在环则无法完成所有课程的学习。
课程表 II 问题的要求是什么？
课程表 II 问题要求返回学习所有课程的顺序，如果不可能完成所有课程，则返回空数组。
➡️
