无向图判断是否存在闭环

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;
        }