目录

 一、原理

1. 引例：207.课程表

 2. 应用场景

3. 代码思路

二、代码模板

三、练习

1、210.课程表Ⅱ🟢

2、2392.给定条件下构造举证🟡

3、310.最小高度树🟡

4、 2603.收集树中金币 🔴

就如大学课程安排一样，如果要学习数据结构与算法、机器学习这类课程，肯定要先学习C语言、Python、离散数学、概率论等等，我们将类似的“推导”关系建如下有向简单图⬇️

根据节点的入度大小，拓扑排序主要用于处理先后问题(拓扑序列)，以及判断图中是否有环的问题；

用大小为节点个数的数组记录每个节点的入度，用队列存放入度为0的节点，遍历这些节点，将这些节点指向的节点的入度-1，最后在记录入度减为0的节点，重复上述步骤；

①拓扑序列：在循环过程中向一数组中push入度为0的节点，排在数组前的节点即为入度先被减为0的节点；

②是否存在环：若拓扑序列数组大小等于节点总个数则说明图中无环；反之，这说明图有环

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例：

解题思路： 与课程表Ⅰ思路基本一样，依次取出入度为0的节点加入到答案数组中，若数组大小与总结点个数不相同，则说明图中有环，返回空数组。

给你一个 正 整数 k ，同时给你：

两个数组里的整数都是 1 到 k 之间的数字。

你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。

矩阵还需要满足以下条件：

返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。

示例：

解题思路：该题很明显是处理先后的问题，我们分别处理行与列，分别得到行与列拓扑序列，最后通过一个数组转换，将下标作为节点，对应的值作为该节点位于行/列的位置；

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

示例：

解题思路： 本题思路较为复杂，可以大致理解为贪心，证明过程可以参考力扣官方答案。每次去掉节点入度最小的节点，到最后剩余1-2个节点即为可以作为最小高度树的根节点

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

 解题思路：

步骤1： 持续删除没有金币的子树，若该子树没有金币，那么也就没有必要访问这个子树的所有节点（拓扑排序思路，记录各个节点的入度）

步骤2： 因为可以从一个节点查询到离该节点距离为2的所有节点，所以可以将这些可以其他节点间接访问的节点删除；通过连续两次循环，将每次入度为1的叶子节点删除。

 步骤3： 通过上述两个步骤，剩余节点的叶子节点为必须被访问的节点，易证得，从任意节点开始访问所有剩余叶子节点并返回最初节点所经过得边数均为最后这颗树（通过步骤1、2删除节点之后的树）的边数的两倍。