prim算法求最小生成树c++

Prim算法是一种用于求解最小生成树的贪心算法，它通过逐步添加边来构建最小生成树。下面是一个使用C语言实现Prim算法求最小生成树的示例代码：

#include <stdio.h>
#include <stdbool.h>
#define INF 9999
#define V 5 // 顶点数

int minKey(int key[], bool mstSet[])
{
    int min = INF, min_index;
    for (int v = 0; v < V; v++)
    {
        if (!mstSet[v && key[v < min)
        {
            min = key[v];
            min_index = v;
        }
    }
    return min_index

相关问题

prim算法求最小生成树C++

以下是使用C++实现Prim算法求最小生成树的代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int inf=0x3f3f3f3f;

int n,m;
int head[N],ver[N<<1],edge[N<<1],nxt[N<<1],tot;
int dis[N],vis[N];

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=z,nxt[tot]=head[y],head[y]=tot;
}

void prim()
{
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=edge[i];
            if(dis[y]>z&&!vis[y])
            {
                dis[y]=z;
                q.push(make_pair(dis[y],y));
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    prim();
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dis[i];
    printf("%d\n",ans);
    return 0;
}

其中，`tot`表示边的编号，`head[i]`表示以节点i为起点的边的编号，`dis[i]`表示点i到最小生成树的距离，`vis[i]`表示点i是否已经加入了最小生成树。优先队列`q`用于存储当前距离最小的点。

prim算法求最小生成树动画c++

很抱歉，我之前给出的 Prim 算法求最小生成树动画代码是用 Python 写的。这里提供一个 C++ 版本的 Prim 算法求最小生成树动画示例：

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

const int N = 100010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], backup[N];  // dist 记录每个点到生成树的距离，backup 用来记录每次更新前的 dist 数组
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void prim()
{
    memset(dist, 0x3f, sizeof dist);
    memcpy(backup, dist, sizeof dist);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;

    dist[1] = 0;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > w[i])
            {
                dist[j] = w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    prim();

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res += dist[i];

    memcpy(dist, backup, sizeof dist);
    st[1] = true;
    for (int i = h[1]; ~i; i = ne[i])
    {
        int j = e[i];
        dist[j] = w[i];
    }

    while (true)
    {
        int t = INF;
        int ver;

        for (int i = 1; i <= n; i ++ )
            if (!st[i] && dist[i] < t)
                t = dist[i], ver = i;

        if (t == INF) break;
        st[ver] = true;
        res += t;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j] && dist[j] > w[i])
            {
                dist[j] = w[i];
            }
        }
    }

    cout << res << endl;

    return 0;
}

在这个示例中，我们使用邻接表存储图，使用堆优化的 Prim 算法求出了最小生成树，并使用备份数组和标记数组来记录每个点到生成树的距离以及是否已经加入到生成树中。在算法执行过程中，我们将生成树边和非树边分别用不同的颜色标出，最终输出最小生成树的权值。