day54 代码随想录算法训练营 图论专题8

1 今日打卡拓扑排序 117. 软件构建dijkstra朴素版 47. 参加科学大会第六期模拟笔试2 拓扑排序2.1 思路构建图 统计入度用邻接表umap存储每个节点的后继节点比如 S 的后继是 T。用数组inDegree统计每个节点的入度指向该节点的边数即该节点依赖的文件数。初始化队列将所有入度为 0 的节点无依赖的文件加入队列。处理队列取出队列中的节点处理该文件加入结果列表。遍历该节点的所有后继节点被该文件依赖的文件将它们的入度减 1因为依赖的文件已处理。如果某个后继节点入度变为 0所有依赖都已处理加入队列。结果判断如果结果列表的长度等于节点数N无环输出顺序。否则存在环相互依赖输出 - 1。2.2 实现代码import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(), m sc.nextInt(); // n文件数m依赖关系数 // 1. 初始化邻接表存储图每个节点对应一个列表存后继节点 ListListInteger umap new ArrayList(); for(int i 0; i n; i) { umap.add(new ArrayList()); } // 2. 初始化入度数组统计每个节点的入度依赖数 int[] inDegree new int[n]; for(int i 0; i m; i) { int start sc.nextInt(), end sc.nextInt(); // S→TT依赖S umap.get(start).add(end); // 邻接表添加边start的后继是end inDegree[end]; // end的入度1多了一个依赖 } // 3. 初始化队列入度为0的节点无依赖的文件入队 QueueInteger que new LinkedList(); ListInteger res new ArrayList(); // 存储拓扑排序结果 for(int i 0; i n; i) { if(inDegree[i] 0) { que.add(i); } } // 4. 处理队列逐步消除入度为0的节点 while(!que.isEmpty()) { int cur que.poll(); // 取出当前处理的节点 res.add(cur); // 加入结果列表 // 遍历当前节点的所有后继节点 ListInteger temp umap.get(cur); for(int node : temp) { inDegree[node]--; // 后继节点的入度减1依赖减少一个 if(inDegree[node] 0) { // 所有依赖都处理完了 que.add(node); // 入队等待处理 } } } // 5. 判断结果是否所有节点都处理了无环 if(res.size() n) { // 输出顺序空格分隔 for(int i 0; i n - 1; i) { System.out.print(res.get(i) ); } System.out.println(res.get(n - 1)); }else{ System.out.println(-1); // 有环输出-1 } } }3 dijkstra朴素版3.1 思路初始化记录起点到所有节点的初始最短距离起点到自己为 0到其他节点为 “无穷大”。记录节点是否已确定最短路径避免重复处理。贪心选择每次从未确定最短路径的节点中选当前距离起点最近的节点局部最优。松弛操作通过这个选中的节点更新其邻接节点的最短距离尝试缩短路径。重复直到所有节点的最短路径都被确定或找到终点的最短路径。3.2 实现代码import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc new Scanner(System.in); // 1. 输入基础参数n节点数m边数 int n sc.nextInt(), m sc.nextInt(); // 2. 初始化邻接矩阵存储图的边和权重 // 邻接矩阵adjacencyMatrix[i][j] 表示i到j的边的权重无穷大表示无直接边 int[][] adjacencyMatrix new int[n1][n1]; for(int i 0; i n; i) { // 初始化为无穷大Integer.MAX_VALUE表示初始时所有节点间无直接边 Arrays.fill(adjacencyMatrix[i], Integer.MAX_VALUE); } // 3. 填充邻接矩阵输入m条边 for(int i 0; i m; i) { int from sc.nextInt(), to sc.nextInt(); // 边的起点、终点 int weight sc.nextInt(); // 边的权重距离/成本 adjacencyMatrix[from][to] weight; // 记录from→to的权重 } // 4. 初始化最短距离数组和访问标记数组 int[] minDist new int[n 1]; // minDist[i]起点(1)到i的最短距离 Arrays.fill(minDist, Integer.MAX_VALUE); // 初始都是无穷大不可达 boolean[] visited new boolean[n 1]; // visited[i]i的最短路径是否已确定 // 5. 起点初始化起点1到自己的距离为0 int start 1, end n; minDist[start] 0; // 6. 核心迪杰斯特拉主循环遍历n次确定n个节点的最短路径 for(int i 1; i n; i) { // 6.1 贪心选择找未访问的、距离起点最近的节点cur int minVal Integer.MAX_VALUE; // 临时存储当前最小距离 int cur 1; // 临时存储选中的节点 for(int j 1; j n; j) { // 条件未访问 距离起点的距离更小 if(!visited[j] minDist[j] minVal) { minVal minDist[j]; cur j; } } // 6.2 标记cur的最短路径已确定后续不再处理 visited[cur] true; // 6.3 松弛操作通过cur更新其邻接节点的最短距离 for(int j 1; j n; j) { // 条件 // 1. j未访问最短路径未确定 // 2. cur到j有直接边不是无穷大 // 3. 起点→cur→j的路径 比 起点→j的当前最短路径 更短 if(!visited[j] adjacencyMatrix[cur][j] ! Integer.MAX_VALUE adjacencyMatrix[cur][j] minDist[cur] minDist[j]) { // 更新最短距离松弛 minDist[j] adjacencyMatrix[cur][j] minDist[cur]; } } } // 7. 输出结果判断终点是否可达 if(minDist[n] Integer.MAX_VALUE) { System.out.println(-1); // 不可达输出-1 }else{ System.out.println(minDist[end]); // 输出起点1到终点n的最短距离 } sc.close(); } }