c++最小生成树的 Prim算法 Kruskal算法

Prim算法和Kruskal算法都是用来解决最小生成树问题的算法，它们的思路和实现都有所不同。

Prim算法的基本思路是从一个顶点开始，每次找到一个与当前生成树相连的权值最小的边所连接的顶点，并将该顶点加入到生成树中，直到所有的顶点都被加入到生成树中为止。

Kruskal算法则是按照边的权值从小到大的顺序来加入边，每次加入一条边之前，判断这条边所连接的两个顶点是否在同一个连通块中，如果不在，则将这条边加入到生成树中，直到生成树中有n-1条边为止。

两种算法都能够求出最小生成树，但是它们的实现方式和时间复杂度略有不同。Prim算法的时间复杂度为O(n^2)，适用于稠密图；而Kruskal算法的时间复杂度为O(m log m)，适用于稀疏图。

相关问题

能否提供一段简洁的C++代码实现Prim算法或Kruskal算法来求解最小生成树？

当然可以。这里分别给出Prim算法和Kruskal算法的简化版C++实现：

**Prim算法（邻接矩阵表示）：**

#include <vector>
#include <queue>

// 定义边的数据结构
struct Edge {
    int u, v, weight;
};

class Graph {
private:
    std::vector<std::vector<Edge>> adjMatrix; // 邻接矩阵

public:
    void prim(int start) {
        std::vector<bool> visited(adjMatrix.size(), false);
        visited[start] = true;
        int minDistance = 0;
        std::priority_queue<pair<int, int>, std::vector<pair<int, int>>, greater<pair<int, int>>> pq;

        pq.push({0, start});
        while (!pq.empty()) {
            int currEdgeWeight = pq.top().first;
            int currNode = pq.top().second;
            pq.pop();

            if (visited[currNode]) continue;

            for (int i = 0; i < adjMatrix[currNode].size(); ++i) {
                Edge e = adjMatrix[currNode][i];
                if (!visited[e.v] && e.weight < minDistance) {
                    minDistance = e.weight;
                    pq.push({minDistance, e.v});
                    visited[e.v] = true;
                }
            }
        }

        // 输出最小生成树的所有边
        for (int node = 0; node < adjMatrix.size(); ++node)
            if (visited[node])
                for (const Edge &edge : adjMatrix[node])
                    if (!visited[edge.v])
                        std::cout << "Edge from " << node << " to " << edge.v << " with weight " << edge.weight << "\n";
    }
};

**Kruskal算法（边集表示）：**

#include <vector>
#include <set>
#include <utility>

struct Edge {
    int u, v, weight;
};

bool compareEdges(const Edge &a, const Edge &b) {
    return a.weight < b.weight;
}

void kruskal(int vertices) {
    std::vector<Edge> edges;
    // 假设通过某种方式填充edges向量
    std::sort(edges.begin(), edges.end(), compareEdges);

    std::vector<int> parent(vertices, -1), rank(vertices, 0);
    std::set<int> forest;

    for (const auto &e : edges) {
        int x = find(e.u, parent);
        int y = find(e.v, parent);

        if (x != y) {
            if (rank[x] > rank[y]) {
                parent[y] = x;
                rank[x] += rank[y];
            } else {
                parent[x] = y;
                if (rank[x] == rank[y]) rank[y]++;
            }
            forest.erase(y); // 如果y已经加入森林，则需要更新集合
            if (forest.count(x) == 0) forest.insert(x); // 添加x到集合，如果之前不在
        }
    }

    // 输出最小生成树的所有边
    for (const auto &edge : edges)
        if (parent[edge.u] != parent[edge.v])
            std::cout << "Edge from " << edge.u << " to " << edge.v << " with weight " << edge.weight << "\n";

    return;
}

int find(int x, std::vector<int> &parent) {
    if (parent[x] != -1) return find(parent[x], parent);
    return x;
}

c++分别用Prim算法和Kruskal算法编程实现一下连通无向图的最小生成树。

好的，下面分别给出使用 Prim 算法和 Kruskal 算法实现连通无向图的最小生成树的 C++ 代码实现。

首先，我们需要定义一个边的结构体，用于存储边的起点、终点和权重：

struct Edge {
    int src, dest, weight;
};

接下来，我们分别实现 Prim 算法和 Kruskal 算法。

使用 Prim 算法实现最小生成树：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// 定义边
struct Edge {
    int src, dest, weight;
};

// 定义比较函数，用于优先队列
struct Compare {
    bool operator()(Edge const& e1, Edge const& e2) {
        return e1.weight > e2.weight;
    }
};

// 定义 Prim 算法函数
void primMST(vector<vector<int>>& graph, int n) {
    vector<int> key(n, INT_MAX);
    vector<bool> mstSet(n, false);
    priority_queue<Edge, vector<Edge>, Compare> pq;

    key[0] = 0;
    pq.push({0, 0, 0});

    while (!pq.empty()) {
        int u = pq.top().dest;
        pq.pop();

        if (mstSet[u]) continue;

        mstSet[u] = true;
        for (int v = 0; v < n; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                key[v] = graph[u][v];
                pq.push({u, v, key[v]});
            }
        }
    }

    int sum = 0;
    for (int i = 1; i < n; i++) {
        sum += key[i];
    }

    cout << "Prim算法得到的最小生成树权值和为 " << sum << endl;
}

// 测试函数
int main() {
    int n = 5;
    vector<vector<int>> graph = {
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0}
    };

    primMST(graph, n);
    return 0;
}

使用 Kruskal 算法实现最小生成树：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义边
struct Edge {
    int src, dest, weight;
};

// 定义比较函数，用于排序
bool compare(Edge const& e1, Edge const& e2) {
    return e1.weight < e2.weight;
}

// 定义 Kruskal 算法函数
void kruskalMST(vector<Edge>& edges, int n) {
    vector<Edge> result(n - 1);
    sort(edges.begin(), edges.end(), compare);
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int e = 0, i = 0;
    while (e < n - 1) {
        Edge next_edge = edges[i++];
        int x = parent[next_edge.src];
        int y = parent[next_edge.dest];
        if (x != y) {
            result[e++] = next_edge;
            for (int j = 0; j < n; j++) {
                if (parent[j] == y) {
                    parent[j] = x;
                }
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += result[i].weight;
    }

    cout << "Kruskal算法得到的最小生成树权值和为 " << sum << endl;
}

// 测试函数
int main() {
    int n = 5;
    vector<Edge> edges = {
        {0, 1, 2},
        {0, 3, 6},
        {1, 2, 3},
        {1, 3, 8},
        {1, 4, 5},
        {2, 4, 7},
        {3, 4, 9}
    };

    kruskalMST(edges, n);
    return 0;
}

以上代码中，我们分别实现了 Prim 算法和 Kruskal 算法。在 Prim 算法中，我们使用了一个优先队列来维护当前最小的边，同时使用了一个 `key` 数组来记录每个节点到当前生成树的最小边权值。在 Kruskal 算法中，我们使用了一个并查集来维护当前生成树。

在测试函数中，我们定义了一个无向图，然后分别调用了 Prim 算法和 Kruskal 算法来计算最小生成树的权值和，最终输出结果。

希望这个代码能够帮助到您！