普利姆最小生成树算法

普利姆最小生成树算法是一种常用的求解带权无向图的最小生成树的算法，它的基本思想是从图中任意选取一个顶点作为起始点，将这个点加入到最小生成树中，然后将与它相邻的边中权值最小的那条边加入到最小生成树中。接着，再将新加入的这个顶点和它相邻的边中权值最小的边加入到最小生成树中，以此类推，直到所有顶点都被加入到最小生成树中。

具体实现方法可以使用堆优化的Prim算法，时间复杂度为O(ElogV)，其中E为边数，V为顶点数。

相关问题

普利姆最小生成树算法c++

普利姆最小生成树算法（Prim's algorithm）是一种用来求解无向图的最小生成树的算法，它采用的是贪心策略。该算法的基本思想是：从任意一个顶点开始，不断地将与当前最小生成树集合相邻的、且权值最小的边加入到最小生成树集合中，直至所有顶点都加入到最小生成树集合中。

以下是普利姆算法的C++代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct Edge
{
    int u,v,w;
}e[maxn];//边 
int n,m;
int dis[maxn],vis[maxn],ans;//dis数组记录某个点到已有的最小生成树集合的距离 
vector<int> G[maxn];//邻接表 
void prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis=0;//从1号点开始扩展 
    priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > > q;//小根堆 
    q.push(make_pair(0,1));//把1号点和0放入小根堆 
    while(!q.empty())
    {
        pair<int,int> now=q.top();
        q.pop();
        if(vis[now.second]) continue;//如果这个点已经被访问过了，就跳过 
        vis[now.second]=1;//标记为已访问 
        ans+=now.first;//累加权值 
        for(int i=0;i<G[now.second].size();i++)
        {
            int v=G[now.second][i];
            if(dis[v]>e[v].w&&!vis[v])
            {
                dis[v]=e[v].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        G[e[i].u].push_back(i);//加入邻接表 
        G[e[i].v].push_back(i);
    }
    prim();
    printf("%d",ans);
    return 0;
}

c++普利姆最小生成树算法

下面是C++实现的Prim最小生成树算法，具体思路和实现过程如下：

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

const int MAX = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大

int graph[MAX][MAX]; // 图的邻接矩阵
int lowcost[MAX]; // 记录从U到V-U具有最小代价的边
int closest[MAX]; // 记录最小边在U中的顶点
bool vis[MAX]; // 标记顶点是否已经加入U
int n; // 顶点数

void prim(int start) {
    memset(vis, false, sizeof(vis)); // 初始化标记数组
    vis[start] = true; // 将起点加入U
    for (int i = 1; i <= n; i++) {
        lowcost[i] = graph[start][i]; // 初始化lowcost数组
        closest[i] = start; // 初始化closest数组
    }
    for (int i = 1; i < n; i++) { // 循环n-1次
        int mincost = INF, v = -1;
        for (int j = 1; j <= n; j++) { // 找到距离U最近的顶点
            if (!vis[j] && lowcost[j] < mincost) {
                mincost = lowcost[j];
                v = j;
            }
        }
        if (v == -1) return; // 如果找不到，退出循环
        vis[v] = true; // 将v加入U
        cout << closest[v] << " " << v << endl; // 输出最小生成树的边
        for (int j = 1; j <= n; j++) { // 更新lowcost和closest数组
            if (!vis[j] && graph[v][j] < lowcost[j]) {
                lowcost[j] = graph[v][j];
                closest[j] = v;
            }
        }
    }
}

int main() {
    // 读入图的邻接矩阵和顶点数
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> graph[i][j];
        }
    }
    prim(1); // 从1号顶点开始构建最小生成树
    return 0;
}