Minimum Spanning Tree

1584. 连接所有点的最小费用

方法一：Kruskal算法

1. 依次选择权值最小的边
2. 如果要加入的边会使得图形成环，则跳过
3. 使用并查集来判断是否会形成环
   1. 如果两个顶点不在同一个子图中，连接边不会形成环
   2. 如果两个顶点在同一个子图中，连接边会形成环
   3. 恰好可以用union解决

比如有三个顶点，1，2，3那么所有的边为(1,2),(1,3),(2,3)

int[][] edges = new int[n * (n - 1) / 2][3];

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // edge[0]:顶点1，edge[1]:顶点2，edge[2]:权值(举例)
        int[][] edges = new int[n * (n - 1) / 2][3];

        int index = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                edges[index++] = new int[]{i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])};
        return kruskal(edges, n);
    }

    private int kruskal(int[][] edges, int n) {
        int res = 0;
        init(n);
        Arrays.sort(edges, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        for (int[] edge : edges) {
            int node1 = edge[0], node2 = edge[1];
            if (union(node1, node2)) { // node1与node2不在同一个子图中，加入这条边不会形成环
                res += edge[2];
            }
        }
        return res;
    }
    int[] parent;
    private boolean union(int i, int j) {
        int rootI = findParent(i), rootJ = findParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
            return true;
        }
        return false;
    }

    private int findParent(int i) {
        if (i != parent[i])
            parent[i] = findParent(parent[i]);
        return parent[i];
    }

    private void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
}

面试用：节点多，边少的时候用 稠密图

方法二：Prim算法

误区：以下是prim，prim需要更新的是已选顶点集距离未选顶点的最短距离

for (int j = 0; j < n; ++j)
    if (!visited[j] && dist[j] > graph[minIndex][j])
        dist[j] = graph[minIndex][j];

以下是dijkstra

for (int j = 1; j <= n; ++j)
    if (!visited[j] && dist[j] > graph[minIndex][j] + minDist)
        dist[j] = graph[minIndex][j] + minDist;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, index = 0;
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                graph[i][j] = graph[j][i] = getMDistance(points[i], points[j]);
        return prim(graph, n);
    }

    private int prim(int[][] graph, int n) {
        int res = 0, inf = Integer.MAX_VALUE >> 1;
        // 已选顶点集距离未选顶点的距离
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        for (int i = 1; i < n; ++i)
            dist[i] = inf;
        for (int i = 0; i < n; ++i) {
            int minIndex = -1, minDist = inf;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minIndex = j;
                }
            }
            visited[minIndex] = true;
            res += minDist;
            for (int j = 0; j < n; ++j)
                if (!visited[j] && dist[j] > graph[minIndex][j])
                    dist[j] = graph[minIndex][j];
        }
        return res;
    }

    public int getMDistance(int[] d1, int[] d2) {
        return Math.abs(d1[0] - d2[0]) + Math.abs(d1[1] - d2[1]);
    }
}