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

题目链接

Prim算法实现

class Solution {
    
public:
    int minCostConnectPoints(vector<vector<int>> &points) {
    
        int ans = 0;
        int n = points.size();
        // 定义并初始化邻接矩阵
        vector<vector<int> > graph(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
    
            for (int j = i + 1; j < n; ++j) {
    
                int manhattan = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                graph[i][j] = manhattan;
                graph[j][i] = manhattan;
            }
        }
        // isJoined 记录 各节点是否加入树
        // distance 记录 各节点加入树的最低代价
        vector<bool> isJoined(n);
        vector<int> distance(n);

        distance = vector<int>(graph[0]);
        int p = n;

        while (p > 0) {
    
            p--;
            // 选出未加入的 最小代价的 边
            int minDistance = INT32_MAX;
            int index = 0;
            for (int i = 0; i < n; ++i) {
    
                if (!isJoined[i]) {
    
                    if (distance[i] < minDistance) {
    
                        minDistance = distance[i];
                        index = i;
                    }
                }
            }

            isJoined[index] = true;
            ans += minDistance;
            // 更新distance
            for (int i = 0; i < n; ++i) {
    
                if (distance[i] > graph[index][i]) {
    
                    distance[i] = graph[index][i];
                }
            }
        }

        return ans;
    }
};

Prim算法时间复杂度O(|V|^2), 适用于边稠密图 (|E|大)

Kruskal算法

class Edge {
    
public:
    Edge(int w, int s, int e) {
    
        this->weight = w;
        this->start = s;
        this->end = e;
    }

    int weight;
    int start;
    int end;
};

bool compare(Edge e1, Edge e2) {
    
    return e1.weight < e2.weight;
}

class UnionFind {
    

public:
    vector<int> nums;

    vector<int> rank;
    explicit UnionFind(int n) {
    
        this->nums = vector<int>(n);
        this->rank = vector<int>(n);
        for (int i = 0; i < nums.size(); ++i) {
    
            this->nums[i] = i;
            this->rank[i] = 1;
        }
    }

    void merge(int i, int j) {
    
        int p = find(j);
        int q = find(i);
        if (rank[p] > rank[q]) {
    
            swap(p, q);
        }
        this->nums[p] = q;
        this->rank[q] += this->rank[p];

    }

    int find(int x) {
    
        if (x == nums[x]) {
    
            return x;
        }
        return find(nums[x]);
    }

    bool check(int i, int j) {
    
        return find(i) == find(j);
    }
};

class Solution {
    
public:
    int minCostConnectPoints(vector<vector<int>> &points) {
    
        vector<Edge> edges;
        int n = points.size();
        int ans = 0;

        for (int i = 0; i < n; ++i) {
    
            for (int j = i + 1; j < n; ++j) {
    
                int distance = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
                edges.emplace_back(distance, i, j);
            }
        }
        sort(edges.begin(), edges.end(), compare);

        UnionFind uf(n);
        for (auto & edge : edges) {
    
            int w = edge.weight;
            int start = edge.start;
            int end = edge.end;
            if (!uf.check(start, end)) {
    
                uf.merge(start, end);
                ans += w;
            }
        }

        return ans;
    }
};

Kruskal算法的时间复杂度为O(ElogE), Kruskal算法适用于边稀疏而顶点较多的图。