写在前:拓扑排序本质是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];
}
网友评论