给一个bfs困难算法关于学校题材的问题并给出java题解
时间: 2024-01-23 21:03:59 浏览: 37
问题描述:
假设你是一名学校的校长,你需要安排最少的考试时间来安排所有的课程。每个课程都必须在一天内完成,而且一天只能进行一场考试。每个课程都有一些必须先修的课程,因此安排一个课程之前必须先安排所有先修课程的考试。给定课程的总数和它们的先修关系列表,你需要编写一个算法来计算完成所有课程所需的最短时间。
输入格式:
第一行包含两个整数numCourses和prerequisites.length,分别表示课程数目和先修关系数目。
接下来prerequisites.length行,每行包含两个整数u和v,表示课程u的先修课程是v。
输出格式:
如果无法完成所有课程,则输出空列表[];否则,按照完成所有课程所需的最短时间的顺序,返回一个课程列表。
算法思路:
这是一个典型的拓扑排序问题,可以使用BFS算法解决。首先,我们需要建立一个图来表示课程之间的依赖关系,并计算每个课程的入度。然后,我们将所有入度为0的课程加入队列中,并在处理它们时,将它们的后继课程的入度减1。如果某个课程的入度为0,则将其加入队列中。当队列为空时,我们就处理完了所有的课程。如果此时我们已经处理完的课程数小于总课程数,则说明存在环,无法完成所有课程;否则,我们就按照处理顺序返回课程列表即可。
Java代码实现:
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] inDegree = new int[numCourses];
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
adj.add(new ArrayList<>());
}
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj.get(p[1]).add(p[0]);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int[] res = new int[numCourses];
int index = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
res[index++] = course;
for (int c : adj.get(course)) {
if (--inDegree[c] == 0) {
queue.offer(c);
}
}
}
return index == numCourses ? res : new int[0];
}
}
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)