写在前：拓扑排序本质是BFS和贪心算法，是这两种算法在有向图应用的专有名词，即拓扑排序针对有向图问题。参考这里。
-
拓扑排序实际上应用的是贪心算法。贪心算法简而言之：每一步最优，全局就最优。
-
具体到拓扑排序，每一次都从图中删除没有前驱的顶点，这里并不需要真正的做删除操作，我们可以设置一个入度数组，每一轮都输出入度为 0 的结点，并移除它、修改它指向的结点的入度（−1即可），依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除，则说明“不能完成所有课程的学习”。
-
拓扑排序保证了每个活动（在这题中是“课程”）的所有前驱活动都排在该活动的前面，并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网，这里就不展开了。
ps：入度：指向当前节点的节点个数；后继节点：当前节点指向的节点
拓扑排序注意点：
- 拓扑排序的结果不唯一
- 可以检测有向图是否有环（对于无向图是否有环使用并查集这种数据结构）
- 贪心点：让入度为1的点入队
- 删除节点的操作，通过入度数组体现！
算法的基本流程：
- 在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。
- 只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1的结点的入度为 0 ，就继续入队。
- 当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。
在代码具体实现的时候，除了保存入度为 0 的队列，我们还需要两个辅助的数据结构（本质都是数组结构）：
- 邻接表：通过结点的索引，我们能够得到这个结点的后继结点，注：为了避免重复加入，邻接表元素为hashset类型
- 入度数组：通过结点的索引，我们能够得到指向这个结点的结点个数。
这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。
应用场景：任务调度计划、课程安排
1.课程表（207 - 中）
题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的
代码实现：
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 0) return false;
// 不需要先修课程
if (prerequisites.length == 0) return true;
int[] inDegree = new int[numCourses];
HashSet<Integer>[] adj = new HashSet[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new HashSet<>();
}
// 遍历邻边，得到入度数组和邻接表
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj[p[1]].add(p[0]);
}
Queue<Integer> queue = new LinkedList<>();
// 加入入度为0的节点
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// 记录已经出队的课程数量（选修的课程数）
int cnt = 0;
while (!queue.isEmpty()) {
Integer top = queue.poll();
cnt++;
// 遍历当前节点的所有后继节点
for (int successor : adj[top]) {
// ps：通过重置后继几点的入度数组，“删除”top节点
inDegree[successor]--;
if (inDegree[successor] == 0) {
queue.add(successor);
}
}
}
return cnt == numCourses;
}
2.课程表II（210 - 中）
题目描述：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的
代码实现：
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses <= 0) return new int[0];
int[] inDegree = new int[numCourses];
HashSet<Integer>[] adj = new HashSet[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new HashSet<>();
}
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj[p[1]].add(p[0]);
}
int cnt = 0;
int[] ans = new int[numCourses];
Queue<Integer> queue = new LinkedList<>();
// 入度为0的节点入队列
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// 当前课程修完，并加入结果集
while (!queue.isEmpty()) {
Integer top = queue.poll();
ans[cnt] = top;
cnt++;
for (int successor : adj[top]) {
inDegree[successor]--;
if (inDegree[successor] == 0) {
queue.add(successor);
}
}
}
if (cnt == numCourses) return ans;
return new int[0];
}
网友评论