prims算法（prims算法核心代码）

编程日记 • 2025-04-17 18:11 • 阅读 50
//这里使用无向图
#include <iostream>

using namespace std;

const int MAXN = 2001;
const int INF = 99999999;

int n,e;
int w[MAXN][MAXN];
int mincount[MAXN]; //从初始顶点到该顶点的最小权值


void init()
{
    int i,j;
    int tx,ty;
    for(i = 0; i<=MAXN; i++)
        for(j =0; j<MAXN; j++)
            w[i][j] = INF;

    cin >> n >> e;

    for(i = 1; i<=e; i++)
    {
        cin >> tx >> ty >> w[tx][ty];
        w[tx][ty] = w[ty][tx];
    }
}

void prim(int s)   //从标号为s处开始生成树
{
    int i,j,cnt = 0,min; // cnt 是生成树所有边的权值之和
    int k;
    for(i = 1; i<= n; i++)
        mincount[i] = w[s][i]; //  初始化，设w[1][i]是初始点k到i的最小权值，如果没有就设为INF
    mincount[s] = 0;

    for(i = 1; i < n; i++) //一共有n-1次
    {
        min = INF;
        for(j = 1; j <= n; j++)
        {
            if(mincount[j]!=0 && mincount[j]<min)
            {
                min = mincount[j];
                k = j;        //记录该点
            }
            mincount[k] = 0;//将该点加入到最小生成树中
            cnt += min;   //将这条边权值加入到最小生成树中
            
            for(j = 1;j<=n;j++)  //修正初始点到每个点的最小权值
            {
                  if(w[k][j]<mincount[j])
                        mincount[j] = w[k][j];
            }
        }
    }
    cout << cnt << endl;
}

int main()
{
    init();
    prim(1);
    return 0;
}
prims算法（prims算法核心代码）

相关推荐
