Meng

Graph Summary

BFS

No. title difficulty
207 Course Schedule I/II Medium

DFS

Union Find

Shortest path(unweighted)

  1. Minimum Genetic Mutation

Weighted shortest path

单源最短路经算法

1. Dijkstra’s Algorithm

这个算法其实是贪心，对一个节点， 每次选择最近能到达的点，并且更新临接顶点的最近距离。 因为每次选择最近的点， 所以 Dijkstra 不能够处理负边的情况。

Dijkstra 实现

  1. 邻接矩阵 对每一个点都要扫一遍邻接点，找到最小的。 所以，复杂度 $O(V^2)$
  2. Heap 既然要找到最小的顶点，用heap存信息便可。 这样的复杂度就是 $O(ElogV)$
  3. Java 中 heap 不支update操作 即一个点发现更短的距离需要更新时，无法把当前节点update priority 或者删除重新插入。折中的方法就是保存老的节点不动，在插入一个相同的路径更短的相同节点。 这样使得 算法复杂度到达了 $O(ElogE)$.

    743. Network Delay Time

    class Solution {
 public int networkDelayTime(int[][] times, int N, int K) {
     if(times == null || times.length == 0) return 0;
     int[][] graph = new int[N + 1][N + 1];

     for(int[] row : graph) Arrays.fill(row, -1);
     for(int i = 0; i < times.length; i++) {
        graph[times[i][0]][times[i][1]]= times[i][2];
     }
     PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) ->(a[1] - b[1]));
     pq.offer(new int[]{K, 0});
     Set<Integer> visited = new HashSet<>();

     while(!pq.isEmpty()) {
         int[] cur = pq.poll();
         //if(visited.contains(cur[0])) continue;
         visited.add(cur[0]);
         if(visited.size() == N) return cur[1];
         for(int i = 1; i < graph[0].length; i++) {
             if(graph[cur[0]][i] == -1 || visited.contains(i)) continue;
             int dist = graph[cur[0]][i] + cur[1];
             pq.offer(new int[]{i, dist});
         }
     }
     return -1;
 }
}

Minimum Spinning Tree

Kruskal 算法

Kruskal 算法描述。按照边的长短从小到大排序。 每次选取一个边，尝试加入图中，如果造成环路的话，舍弃改边。 环路的判断可以用union find 来做。

1584. Min Cost to Connect All Points

class Solution {
    public boolean union(int[] tf, int x, int y) {
        int a = find(tf, x);
        int b = find(tf, y);
        if(a == b) return false;
        else {
            tf[b] = a;
            return true;
        }
    }
    public int find(int[] tf, int x) {
        if(tf[x] == x) return x;
        tf[x] = find(tf, tf[x]);
        return tf[x];
    }
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[][] dist = new int[n][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> dist[a[0]][a[1]] - dist[b[0]][b[1]]);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                pq.offer(new int[]{i, j});
            }
        }
        int cnt = n;
        int[] tf  = new int[n];
        for(int i = 0; i < tf.length; i++) tf[i] = i;
        int ret = 0;
        while(!pq.isEmpty() && cnt > 1) {
            int[] point = pq.poll();
            if(union(tf, point[0], point[1])) {
                ret += dist[point[0]][point[1]];
                cnt--;
            }
        }
        return ret;
    }
}

Prim 算法

Prim 算法和 Dijstra 神似。 都是贪心。 但是贪心贪法不同。 Dijkstra 是贪从源点到当前最近的节点。 而prim不需要记录最近的路径。 它只需要每次找出当前点的最近临接点即可。 所以每次往 pq 里面push 是当前点与剩下所有点之间的距离。

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[][] dist = new int[n][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                dist[j][i] = dist[i][j];
            }
        }
        HashSet<Integer> used = new HashSet<>();
        pq.offer(new int[]{0, 0});
        int ret = 0;
        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            if(used.contains(cur[0])) continue;
            ret +=  cur[1];
            used.add(cur[0]);
            if(used.size() == n) return ret;
            for(int i = 0; i < dist[0].length; i++) {
                if(used.contains(i)) continue;
                int path = dist[cur[0]][i];
                pq.offer(new int[]{i, path});
            }
        }
        return -1;
    }
}

Search

    Table of Contents