最小生成树Prim算法详解(C++)-Toy模板网

这篇具有很好参考价值的文章主要介绍了最小生成树Prim算法详解(C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Prim:

Prim算法是一种用于寻找加权无向图的最小生成树的贪心算法。它的基本思路是从图中任意一个点开始，选择与该点相邻的最小边，并将该边所连接的点加入到生成树的集合中。然后再从新加入的点出发，重复该过程直到所有的节点都被加入到生成树中。

邻接表：

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

const int INF = 0x3f3f3f3f;   // 定义一个表示无穷大的值

vector<pair<int, int>> adj[10005];   // 邻接表，用于存储图的边信息
int dist[10005];    // 用于记录从起点到其他各个点的距离
bool vis[10005];    // 用于记录某个点是否已经加入生成树

int prim(int start) {
    memset(dist, INF, sizeof(dist));    // 初始化距离数组为无穷大
    memset(vis, false, sizeof(vis));    // 初始化所有点都未被访问过

    dist[start] = 0;    // 起点到自己的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));   // 将起点加入到优先队列中

    int ans = 0;    // 用于记录最小生成树的总权值

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

        if (vis[u]) continue;    // 如果u已经被访问过，则跳过

        vis[u] = true;    // 将u标记为已访问

        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first;
            int w = adj[u][i].second;

            if (!vis[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(make_pair(dist[v], v));
            }
        }

        ans += dist[u];
    }

    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));    // 由于是无向图，所以要将另一条边也加入邻接表中
    }

    cout << prim(1) << endl;

    return 0;
}

初始化：首先需要初始化距离数组dist和标记数组vis。因为在Prim算法中，我们需要记录从起点到其他各个点的距离，同时还需要记录每个节点是否已经加入到生成树中。这里我们可以使用一个布尔数组vis来记录每个节点的状态，如果某个节点已经被加入到生成树中，那么vis[i]就为true，否则为false。距离数组dist用于记录从起点到每个节点的距离，这里我们将所有距离初始化为无穷大，表示起点到其他各个点的距离都还没有计算过。
将起点加入到优先队列中：在Prim算法中，我们需要从某个点开始，不断选择与该点相邻的最小边，并将该边所连接的点加入到生成树的集合中。因此，我们将起点加入到优先队列中，并将起点到自己的距离dist[start]设为0。这里需要使用一个小根堆priority_queue，来维护到各个节点的距离，以便每次选择最小的距离进行扩展。
不断扩展生成树：在优先队列中每次取出距离起点最近的点u，如果这个点已经被访问过了，则直接跳过。否则，将u标记为已经访问过，并将从u出发的所有边中，与还未加入到生成树中的节点中距离最小的那条边加入到生成树中，并将该节点加入到优先队列中。
计算最小生成树的权值：在Prim算法中，每次加入一条边都会产生一个权值，因此，需要用一个变量ans来记录最小生成树的权值，每次将新加入的边的权值累加到ans中。
返回最小生成树的权值：当优先队列为空时，表示所有节点都已经加入到生成树中了，此时可以返回ans作为最小生成树的权值。

总结：Prim算法的实现过程比较简单，主要就是使用一个优先队列来维护到各个节点的距离，并不断从优先队列中选择距离起点最近的点，然后将从该点出发的所有边中，与还未加入到生成树中的节点中距离最小的那条边加入到生成树中，不断重复这个过程直到所有节点都加入到生成树中为止。

邻接矩阵：

#include<bits/stdc++.h>
using namespace std;
#define inf 1e8 // 定义一个无穷大的常量

const int MAXN = 1005;

int graph[MAXN][MAXN]; // 邻接矩阵
int dis[MAXN]; // 存储顶点到生成树的距离
bool vis[MAXN]; // 标记顶点是否已经加入到生成树中

int Prim(int n) { // n为图的顶点数
    int ans = 0;
    memset(vis, false, sizeof(vis)); // 初始化标记数组为false
    memset(dis, inf, sizeof(dis)); // 初始化到生成树距离为无穷大
    dis[1] = 0; // 从任意一个点开始都可以
    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (u == -1 || dis[u] > dis[j])) { // 找到未加入生成树的距离最小的点
                u = j;
            }
        }
        vis[u] = true; // 将找到的点加入生成树
        ans += dis[u]; // 将距离加入到答案中
        for (int v = 1; v <= n; ++v) {
            if (!vis[v] && graph[u][v] < dis[v]) { // 更新未加入生成树的点到生成树的距离
                dis[v] = graph[u][v];
            }
        }
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图的顶点数和边数
    memset(graph, inf, sizeof(graph)); // 初始化邻接矩阵中的距离为无穷大
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入边的两个端点和边的权值
        graph[u][v] = graph[v][u] = w; // 更新邻接矩阵
    }
    int ans = Prim(n); // 计算最小生成树的权值和
    cout << ans << endl;
    return 0;
}

该代码使用了邻接矩阵来表示图，并使用了一个dis数组来存储每个点到生成树的距离，以及一个vis数组来标记每个点是否已经加入到生成树中。Prim算法的具体实现过程如下：

该算法需要对所有的n个点进行n次扫描，每次扫描都需要对剩余的n个点进行比较。而每次更新dis数组时，需要遍历所有的n个点。因此，该算法的时间复杂度为O(n^2)。

需要注意的是，该算法使用了一个dis数组来存储每个点到生成树的距离，而每次找到距离最小的点时，需要遍历所有未加入生成树的点。这种遍历未加入生成树的点的方式虽然看似效率低下，但实际上并不会影响算法的时间复杂度，因为在每次遍历时，只有一个点被加入到生成树中，因此下一次遍历时，该点就不再被考虑。因此，该算法的时间复杂度仍然为O(n^2)。

评价:

Prim算法的时间复杂度与实现方式有关。如果采用邻接矩阵的方式来表示图，那么Prim算法的时间复杂度就是O(V^2)，其中V是图的顶点数。因为在邻接矩阵中，我们需要遍历每一个点，以确定该点是否已经加入到生成树中，并找到连接该点的最小边。这个过程的时间复杂度是O(V^2)，因此Prim算法的总时间复杂度就是O(V^2)。

但是如果采用邻接表的方式来表示图，那么Prim算法的时间复杂度就是O(ElogV)，其中E是图的边数，V是图的顶点数。因为在邻接表中，我们可以直接访问与某个点相邻的边，并找到连接该点的最小边，这个过程的时间复杂度是O(logV)，因此Prim算法的总时间复杂度就是O(ElogV)。