无向图判断是否存在闭环
public boolean findRedundantConnection(int[][] edges) { int[] parent = new int[edges.length+1]; //将每个节点的父节点标记为自己 for (int i = 0; i < parent.length; i++) parent[i] = i; //对每一条边进行遍历 for (int[] edge: edges){ int f = edge[0], t = edge[1]; //如果两条边有共同的祖先,则返回true if (find(parent, f) == find(parent, t)) return true; //否就更新该初始节点的祖先,让该祖先能到结束节点的祖先 else parent[find(parent, f)] = find(parent, t); } return false; } //找到该节点的祖先,并一路更新值 private int find(int[] parent, int f) { if (f != parent[f]) { parent[f] = find(parent, parent[f]); } return parent[f]; }
单源最短路径
public void Dijkstra(int[][] times, int N, int K) { //将每条边存入 HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>(); //记录到每个点的最短路径 HashMap<Integer, Integer> dist = new HashMap<>(); for (int i = 0; i < N; i++) { dist.put(i, Integer.MAX_VALUE); graph.put(i, new ArrayList<>()); } dist.put(K, 0); for (int[] each : times) { graph.get(each[0]).add(new int[]{each[1], each[2]}); } //是否用过某个点 boolean[] seen = new boolean[N]; while (true) { //在没用过的点中,寻找最短的下个点 int nextStep = -1, nextDist = Integer.MAX_VALUE; for (int i = 0; i < N; i++) { if (!seen[i] && dist.get(i) < nextDist) { nextDist = dist.get(i); nextStep = i; } } if (nextStep == -1) break; seen[nextStep] = true; //以该点为起点,更新每个点的最短路径 if (graph.containsKey(nextStep)) { for (int[] rows : graph.get(nextStep)) { dist.put(rows[0], Math.min(dist.get(rows[0]), dist.get(nextStep) + rows[1])); } } } for (Map.Entry<Integer, Integer> entry : dist.entrySet()) { if (entry.getValue() == Integer.MAX_VALUE) System.out.println("到点" + entry.getKey() + "无法抵达"); else System.out.println("到点" + entry.getKey() + "距离为:" + entry.getValue()); } }
有向图寻找不会进入闭环的点
public List<Integer> eventualSafeNodes(int[][] graph) { List<Integer> res = new ArrayList<>(); if(graph == null || graph.length == 0) return res; int nodeCount = graph.length; int[] color = new int[nodeCount]; for(int i = 0;i < nodeCount;i++){ if(dfs(graph, i, color)) res.add(i); } return res; } public boolean dfs(int[][] graph, int start, int[] color){ if(color[start] != 0) return color[start] == 1; color[start] = 2; for(int newNode : graph[start]){ if(!dfs(graph, newNode, color)) return false; } color[start] = 1; return true; }