Day 56 总结
- 自己实现中遇到哪些困难
- 今日收获，记录一下自己的学习时间
- 18:00 - ？？？
拓扑排序
- 节点存在依赖关系，对这些依赖进行线性规划
- 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序
- BFS实现
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
-
判断有环
-
当不存在入度为0的节点时，结果集元素个数 不等于 图中节点个数，存在环
-
-
代码
-
记录度数
-
收集结果
-
图的构建
-
117 软件构建
题目连接： 117. 软件构建
题目描述：
文件 0 - N-1， 文件之间存在依赖关系，确定文件处理顺序。
输入：
N 个文件， M个依赖关系 + S -> T
输出：
按序处理文件的顺序
实现思路：
BFS法，找到入度为0的节点，删除其依赖，加入结果集。
public class Main {public static void main (String[] args){new Main().solve();}public void solve() {Scanner in = new Scanner(System.in);int N = in.nextInt();int[] degreess = new int[N];int[][] graph = new int[N][N];int[] res = new int[N];int[] visited = new int[N];// 获取图的信息，记录入度int M = in.nextInt();for (int i=0; i<M; i++) {int S = in.nextInt();int T = in.nextInt();graph[S][T] = 1;degreess[T]++;}// 拓扑排序for (int i=0; i<N; i++) {// 挑选入度为0的节点int node = -1;for (int j=0; j<N; j++) {if (visited[j] == 0 && degreess[j] == 0){node = j;visited[node] = 1;break;}}// 遇到环if (node == -1) {System.out.println(-1);return;}// 将该几点从图中移除for (int j=0; j<N; j++) {if (graph[node][j] == 1) {degreess[j] --;}}// 添加至结果集合res[i] = node;}for (int i=0; i<N-1; i++)System.out.print(res[i] + " ");System.out.println(res[N-1]);}}
