拓扑排序精讲
题目讲解：代码随想录
重点：
- 给出一个有向图，把这个有向图转成线性的排序就叫拓扑排序。
- 拓扑排序也是图论中判断有向无环图的常用方法。
- 拓扑排序的过程，其实就两步：
· 找到入度为0的节点，加入结果集。
· 将该节点从图中移除（也就是减少影响的inDegree数组）。思路：
- 把最开始入度为0的点推入队列, 作为拓扑排序的入口
Deque<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) {if (inDegree[i] == 0) queue.offer(i); }
- 遍历队列，把当前入度为0的节点加进result，然后更新inDegree数组。如果更新之后该节点也为0, 则推入队列。
while (!queue.isEmpty()) {int cur = queue.poll();result.add(cur);LinkedList<Integer> files = umap.get(cur);if (!files.isEmpty()) {for (Integer file : files) {inDegree[file]--;if (inDegree[file] == 0) queue.offer(file);}} }
public class SoftwareConstruction {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 初始化入度数组, 邻接表int[] inDegree = new int[n];List<LinkedList<Integer>> umap = new ArrayList<>(n);for (int i = 0; i < n; i++) umap.add(new LinkedList<>());for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();inDegree[t]++;umap.get(s).add(t);}// 把最开始入度为0的点推入队列, 作为拓扑排序的入口Deque<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (inDegree[i] == 0) queue.offer(i);}List<Integer> result = new ArrayList<>();// 遍历队列, 把当前入度为0的节点加进result, 然后更新inDegree数组// 如果更新之后该节点也为0, 则推入队列while (!queue.isEmpty()) {int cur = queue.poll();result.add(cur);LinkedList<Integer> files = umap.get(cur);if (!files.isEmpty()) {for (Integer file : files) {inDegree[file]--;if (inDegree[file] == 0) queue.offer(file);}}}// 输出结果if (result.size() == n) {for (int i = 0; i < n - 1; i++) {System.out.print(result.get(i) + " ");}System.out.println(result.get(n - 1));} else {System.out.println(-1);}}
}
Dijkstra（朴素版）精讲
题目讲解：代码随想录
重点：
- Dijkstra三部曲：
选源点到哪个节点近且该节点未被访问过
该最近节点被标记访问过
更新非访问节点到源点的距离（即更新minDist数组）- 在有权图权值非负数中求从起点到其他节点的最短路径算法。
- prim和dijkstra很像，但是prim可以求有负数的有权图，因为prim只求最小生成树，求的不是路径。
思路：
- 初始化minDist, visited和parent
int[] minDist = new int[n + 1]; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[start] = 0; boolean[] visited = new boolean[n + 1]; int[] parent = new int[n + 1]; Arrays.fill(parent, -1);
- 根据minDist选距离源点最近的节点
for (int v = 1; v <= n; v++) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;} }
- 标记当前节点已访问
visited[cur] = true;
- 更新与当前节点相连的非访问节点的minDist和parent数组
for (int v = 1; v <= n; v++) {if (!visited[v] && graph[cur][v] != Integer.MAX_VALUE && minDist[cur] + graph[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + graph[cur][v];parent[v] = cur;} }
public class AttendScienceConference {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] graph = new int[n + 1][n + 1];;for (int i = 0; i < n + 1; i++) {Arrays.fill(graph[i], Integer.MAX_VALUE);}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int e = scanner.nextInt();int v = scanner.nextInt();graph[s][e] = v;}int start = 1;int end = n;// 初始化minDist, visited和parentint[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;boolean[] visited = new boolean[n + 1];int[] parent = new int[n + 1];Arrays.fill(parent, -1);// 最多遍历所有节点就可以获取到所有的最短路径for (int i = 1; i <= n; i++) {int minVal = Integer.MAX_VALUE;int cur = start;// 1. 根据minDist选距离源点最近的节点for (int v = 1; v <= n; v++) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// 2. 标记当前节点已访问visited[cur] = true;// 3. 更新与当前节点相连的非访问节点的minDist和parent数组for (int v = 1; v <= n; v++) {if (!visited[v] && graph[cur][v] != Integer.MAX_VALUE && minDist[cur] + graph[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + graph[cur][v];parent[v] = cur;}}}// 输出结果if (minDist[end] == Integer.MAX_VALUE) System.out.println(-1);else System.out.println(minDist[end]);for (int i = 1; i <= n; i++) {System.out.println(parent[i] + "->" + i);}}
}
Dijkstra（堆优化版）精讲
题目讲解：代码随想录
重点：
- 稀疏图求最短路径用邻接表存储图，用优先队列取距源点最近的点。
思路：
- 初始化minDist, visited和PriorityQueue
int[] minDist = new int[n + 1]; Arrays.fill(minDist, Integer.MAX_VALUE); minDist[start] = 0; boolean[] visited = new boolean[n + 1]; PriorityQueue<Pair> pq = new PriorityQueue<>(); pq.add(new Pair(start, 0));
- 选距离源点最近的节点(通过优先级队列来实现
Pair cur = pq.poll();
- 标记当前节点已访问
visited[cur.node] = true;
- 更新与当前节点相连的非访问节点的minDist并推入PriorityQueue
for (Edge edge : graph.get(cur.node)) {if (!visited[edge.to] && minDist[cur.node] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[cur.node] + edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));} }
// 边的类
class Edge {int to;int val;Edge(int to, int val) {this.to = to;this.val = val;}
}
// PriorityQueue中存放的Pair
class Pair implements Comparable<Pair>{int node;int minDistVal;Pair(int node, int minDistVal) {this.node = node;this.minDistVal = minDistVal;}@Overridepublic int compareTo(Pair o) {return Integer.compare(this.minDistVal, o.minDistVal);}
}
public class AttendScienceConferenceHeap {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 背景是稀疏图, 所以用邻接表比较好, 链表存储的是Edge对象List<LinkedList<Edge>> graph = new ArrayList<>(n + 1);for (int i = 0; i < n + 1; i++) {graph.add(new LinkedList<>());}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int e = scanner.nextInt();int v = scanner.nextInt();graph.get(s).add(new Edge(e, v));}int start = 1;int end = n;// 初始化minDist, visited和PriorityQueueint[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;boolean[] visited = new boolean[n + 1];PriorityQueue<Pair> pq = new PriorityQueue<>();pq.add(new Pair(start, 0));// 遍历PriorityQueuewhile (!pq.isEmpty()) {// 1. 选距离源点最近的节点(通过优先级队列来实现)Pair cur = pq.poll();if (visited[cur.node]) continue;// 2. 标记当前节点已访问visited[cur.node] = true;// 3. 更新与当前节点相连的非访问节点的minDist并推入PriorityQueuefor (Edge edge : graph.get(cur.node)) {if (!visited[edge.to] && minDist[cur.node] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[cur.node] + edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));}}}// 输出结果if (minDist[end] == Integer.MAX_VALUE) System.out.println(-1);else System.out.println(minDist[end]);}
}
