LeetCode 拓扑排序 刷题模板
内容提要
拓扑排序是一种对有向无环图（DAG）进行排序的算法，主要用于根据任务依赖关系调度任务。该算法通过删除入度为0的节点并更新相邻节点的入度，直到所有节点被访问。常见应用包括课程安排问题，判断是否可以完成所有课程学习。
延伸解读
拓扑排序与BFS的关系
文章指出拓扑排序的实现基础是广度优先搜索（BFS）。在模板中，使用队列处理入度为0的节点，并逐层更新相邻节点的入度，这与BFS的层序遍历思想一致。理解这一点有助于将拓扑排序视为BFS在有向无环图上的特定应用，从而复用BFS的代码结构。
入度数组与邻接表的构建
模板中通过遍历prerequisites数组来构建入度数组和邻接表。对于每个先修关系[ai, bi]，将bi指向ai的边加入邻接表，并增加ai的入度。这种构建方式直接反映了课程之间的依赖关系，是后续拓扑排序的基础。读者应注意邻接表的初始化，避免空指针。
环检测与结果判断
拓扑排序可用于判断有向图中是否存在环。在课程表问题中，如果最终学习的课程数量等于总课程数，则无环，可以完成；否则存在环，无法完成。课程表II则要求返回具体顺序，若无法完成则返回空数组。这体现了拓扑排序在依赖调度中的实际应用。
模板的通用性与调整
文章提供的Go语言模板具有通用性，可解决课程表I和II。对于课程表I，只需在BFS过程中计数已处理节点，最后判断是否等于总课程数；对于课程表II，则需记录出队顺序。读者可根据具体问题灵活调整模板，如修改返回值或添加额外逻辑。
Q&A
什么是拓扑排序？
拓扑排序是一种对有向无环图（DAG）进行排序的算法，用于根据任务依赖关系调度任务。
拓扑排序的基本算法步骤是什么？
拓扑排序的步骤包括初始化邻接表、将入度为0的节点加入队列、循环处理队列中的节点并更新相邻节点的入度，直到所有节点都访问过。
拓扑排序的入度为0的节点是什么意思？
入度为0的节点是指没有任何边指向该节点的节点，可以直接访问。
拓扑排序有哪些典型应用？
拓扑排序的典型应用包括课程安排问题，判断是否可以完成所有课程学习。
如何判断是否可以完成所有课程的学习？
可以通过拓扑排序判断，如果存在环则无法完成所有课程的学习。
课程表 II 问题的要求是什么？
课程表 II 问题要求返回学习所有课程的顺序，如果不可能完成所有课程，则返回空数组。
