publicint[] findOrder(int numCourses, int[][] prerequisites) { // adjacency list Set<Integer>[] graph = new Set[numCourses]; for (int[] e : prerequisites) { // e[0] depends on e[1] // e[1] --> e[0] if (graph[e[1]] == null) { graph[e[1]] = new HashSet<>(); } graph[e[1]].add(e[0]); }
List<Integer> list = new ArrayList<>(numCourses); boolean[] globalVisited = newboolean[numCourses]; boolean[] localVisited = newboolean[numCourses]; // to check cycle
for (int i = 0; i < numCourses; ++i) { if (!dfs(graph, i, globalVisited, localVisited, list)) { returnnewint[0]; } }
// copy and reverse int[] result = newint[numCourses]; for (int i = 0; i < numCourses; ++i) { result[i] = list.get(numCourses - i - 1); } return result; }
// return: can finish publicbooleandfs(Set<Integer>[] graph, int node, boolean[] globalVisited, boolean[] localVisited, List<Integer> list){ if (localVisited[node]) returnfalse; if (globalVisited[node]) returntrue; localVisited[node] = true; globalVisited[node] = true; Set<Integer> next = graph[node]; if (next != null) { for (Integer n : next) { if (!dfs(graph, n, globalVisited, localVisited, list)) { // return false and exit, no need to reset localVisited returnfalse; } } } localVisited[node] = false; // reset list.add(node); returntrue; }
publicintnetworkDelayTime(int[][] times, int N, int K){ // time[i]: node [i] receive time int[] time = newint[N+1]; Arrays.fill(time, -1); time[K] = 0;
// graph[i]: List<int[]>, [to node, w] List<int[]>[] graph = new List[N+1]; for (int i = 1; i <= N; ++i) { graph[i] = new LinkedList<>(); } for (int[] t : times) { int from = t[0], to = t[1], w = t[2]; graph[from].add(newint[]{to, w}); }
dfs(graph, time, K);
int max = -1; for (int i = 1; i <= N; ++i) { if (time[i] == -1) return -1; max = Math.max(max, time[i]); } return max; }
publicvoiddfs(List<int[]>[] graph, int[] time, int node){ for (int[] t : graph[node]) { int to = t[0], w = t[1]; int newTime = time[node] + w; if (time[to] != -1 && newTime >= time[to]) { continue; } time[to] = newTime; dfs(graph, time, to); } } }
弗洛伊德算法 Floyd-Warshall Algorithm
特点：
可以求任意两个结点之间的最短路。
复杂度较高，但容易实现。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在（不能有个负环）。
思路：
使用矩阵表示节点 u → v 之间的最短路径。
初始化时，w[i][i] 为0， w[i][j] 为边 i → j 的权重，没有边的元素设置为无穷大。
节点 i → j 可能通过 k 中转而缩短距离，遍历计算点 i → k → j 的路径，如果比现有的 i → j 小，则更新，即松弛操作。
publicintnetworkDelayTime(int[][] times, int N, int K){ // w[i][j]: time from [i] to [j], Integer.MAX_VALUE: inf int[][] w = newint[N+1][N+1]; for (int i = 1; i <= N; ++i) { Arrays.fill(w[i], Integer.MAX_VALUE); w[i][i] = 0; }
for (int[] e : times) { int u = e[0], v = e[1], t = e[2]; w[u][v] = t; }
for (int k = 1; k <= N; ++k) { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { int sum; if (w[i][k] == Integer.MAX_VALUE w[k][j] == Integer.MAX_VALUE) { sum = Integer.MAX_VALUE; } else { sum = w[i][k] + w[k][j]; } w[i][j] = Math.min(w[i][j], sum); } } }
int max = -1; for (int j = 1; j <= N; ++j) { if (w[K][j] == Integer.MAX_VALUE) return -1; max = Math.max(max, w[K][j]); } return max; } }
迪杰斯特拉算法 Dijkstra Algorithm
特点：
求单源最短路径。
只适用于非负权图。
时间复杂度优秀。
使用了贪心思想。
步骤：
初始：
已确定最短路的节点为集合P，未确定最短路的节点为集合Q。
保存源节点 K 到每个节点的距离，初始化时距离为无穷大。
将源节点 K 放入Q，其距离为0。
循环：
从Q取出一个距离最短的节点 u，其最短路径已经确定，因此移到P（贪心思想，因为 K 到其他点的距离更远，不可能找到一个经过其他点再到 u 的更短路径）。
松弛 u 的未确定最短路的出节点，即判断经过 u 能否缩短距离。将这些节点放到Q中等待下一轮循环处理。
classSolution{ publicintnetworkDelayTime(int[][] times, int N, int K){ // graph[i]: List<int[]>, [to node, w] List<int[]>[] graph = new List[N+1]; for (int i = 1; i <= N; ++i) { graph[i] = new LinkedList<>(); } for (int[] e : times) { int from = e[0], to = e[1], w = e[2]; graph[from].add(newint[]{to, w}); }
// [distance, node] PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // node --> min distance HashMap<Integer, Integer> dist = new HashMap<>();
heap.offer(newint[]{0, K});
while (heap.size() > 0) { int[] n = heap.poll(); int distance = n[0]; int node = n[1]; if (dist.containsKey(node)) continue; // already determined dist.put(node, distance); // node determined for (int[] g : graph[node]) { int nextNode = g[0]; int w = g[1]; // K --> ... --> node --> nextNode if (dist.containsKey(nextNode)) continue; // alreay determined heap.offer(newint[]{distance + w, nextNode}); } }
if (dist.size() != N) return -1; int max = -1; for (int d : dist.values()) { max = Math.max(max, d); } return max; } }
booleanunion(int x, int y){ // x 与 y 所在家族合并 x = find(x); y = find(y); if (x == y) { // 原本就在一个家族里就不管了 returnfalse; } parent[x] = y; // 把 x 的祖先变成 y 的祖先的儿子 returntrue; }
publicintminimumCost(int N, int[][] connections){ // sort connections by cost from small to large Arrays.sort(connections, (a,b) -> a[2]-b[2]);
int[] parent = newint[N+1]; for (int i = 1; i <= N; ++i) { parent[i] = i; }
int cost = 0; for (int[] edge : connections) { if (union(edge[0], edge[1], parent)) { cost += edge[2]; } }
// check if all the roots are the same int p = -1; for (int i = 1; i <= N; ++i) { int root = findRoot(i, parent); if (p == -1) { p = root; } elseif (p != root) { return -1; } } return cost; }
publicintfindRoot(int x, int[] parent){ while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
publicbooleanunion(int a, int b, int[] parent){ a = findRoot(a, parent); b = findRoot(b, parent); if (a == b) returnfalse; parent[a] = b; returntrue; } }
Prim算法
Kruskal算法每次添加一个最小的边，而Prim算法则是每次添加一个距离已选取节点集最近的点。
流程：
集合S表示已选取的节点集。
选任意一个节点作为起始节点 a，放到集合S中，并更新其他节点到集合S的最近距离。因为当前S中只有一个节点 a，因此更新为到节点 a 的距离。
选取距离S最近的一个节点 b，放到集合S中，并更新其他节点到集合S的最近距离。也就是节点 i 的距离更新为 min { adj[a][i], adj[b][i] }。
// graph[i][j]: // INF: not reachable // x: distance int[][] graph = newint[N+1][N+1]; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (i == j) graph[i][j] = 0; else graph[i][j] = INF; } } for (int[] edge : connections) { int u = edge[0], v = edge[1], w = edge[2]; graph[u][v] = graph[v][u] = w; }
// dist[i] // d: current min distance from one of added nodes // INF: distance is inf, not reachable int[] dist = newint[N+1]; Arrays.fill(dist, INF); // added nodes boolean[] added = newboolean[N+1];
// set node [1] as candidates dist[1] = 0;
int cost = 0; for (int k = 0; k < N; ++k) { // N nodes to add
// find node with min distance int min = INF; int node = -1; for (int i = 1; i <= N; ++i) { if (!added[i] && dist[i] < min) { min = dist[i]; node = i; } }
// no reachable node found if (node == -1) { return -1; }
// update dist[i] with distance from [node] to [i] for (int i = 1; i <= N; ++i) { if (added[i]) continue; if (graph[node][i] == INF) continue; dist[i] = Math.min(dist[i], graph[node][i]); } } return cost; } }
// graph[i].get(j): // x: distance // null: not reachable Map<Integer, Integer>[] graph = new HashMap[N+1]; for (int i = 1; i <= N; ++i) { graph[i] = new HashMap<>(); } for (int[] edge : connections) { int u = edge[0], v = edge[1], w = edge[2]; graph[u].put(v, w); graph[v].put(u, w); }
// add node [1] to the candidate collection heap.offer(newint[]{0, 1});
int cost = 0; for (int k = 0; k < N; ++k) { // N nodes to add
// find node with min distance int[] min = findMin(heap, added);
// no reachable node found if (min == null) { return -1; }
int dist = min[0]; int node = min[1];
// add [node] cost += dist; added[node] = true;
// add candidates with distance from [node] for (int i = 2; i <= N; ++i) { if (added[i]) continue; Integer d = graph[node].get(i); if (d != null) { // d == null: not reachable heap.offer(newint[]{d, i}); } } } return cost; }
publicint[] findMin(PriorityQueue<int[]> heap, boolean[] added) { while (heap.size() > 0) { int[] n = heap.poll(); int node = n[1]; if (!added[node]) { return n; } } returnnull; } }
解法3：通过，67 ms
正在怀疑是不是自己写错了Prim算法的时候，借鉴了评论区的思路，重新优化了邻接表的表示方法，使用 HashMap -> List -> int[] 的形式。
// graph.get(i).get(x): // int[0]: node // int[1]: distance from [i] to [node] Map<Integer, List<int[]>> graph = new HashMap<>(); for (int[] edge : connections) { int u = edge[0], v = edge[1], w = edge[2]; List<int[]> list1 = graph.get(u); if (list1 == null) { list1 = new LinkedList<>(); graph.put(u, list1); } list1.add(newint[]{v,w});
List<int[]> list2 = graph.get(v); if (list2 == null) { list2 = new LinkedList<>(); graph.put(v, list2); } list2.add(newint[]{u,w}); }
// heap: candidates // int[0]: node // int[1]: distance from one of added nodes PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]); // added nodes boolean[] added = newboolean[N+1];
// add node [1] to the candidate collection heap.offer(newint[]{1, 0});
int cost = 0; for (int k = 0; k < N; ++k) { // N nodes to add
// find node with min distance int[] min = findMin(heap, added);
// no reachable node found if (min == null) { return -1; }
int node = min[0]; int dist = min[1];
// add [node] cost += dist; added[node] = true;
// add candidates with distance from [node] List<int[]> list = graph.get(node); if (list != null) { for (int[] e : list) { heap.offer(e); } } } return cost; }
publicint[] findMin(PriorityQueue<int[]> heap, boolean[] added) { while (heap.size() > 0) { int[] n = heap.poll(); int node = n[0]; if (!added[node]) { return n; } } returnnull; } }
classSolution{ publicbooleanisBipartite(int[][] graph){ // 0: uncolored. 1,-1: two oppsite colors int[] colors = newint[graph.length]; for (int i = 0; i < graph.length; ++i) { // skip already colored node if (colors[i] != 0) continue; // set color to 1 colors[i] = 1; // dfs, visit connected components if (!dfs(graph, colors, i)) returnfalse; } returntrue; }
publicbooleandfs(int[][] graph, int[] colors, int node){ int color = colors[node]; int[] nodes = graph[node]; for (int n : nodes) { // found uncolored node, set color to oppsite and search deep if (colors[n] == 0) { colors[n] = -color; if (!dfs(graph, colors, n)) { returnfalse; } } // found node with same color, return false if (colors[n] == color) { returnfalse; } // found node with oppsite color, loop continue } returntrue; } }
