C++实现最小生成树算法

大家好，欢迎来到IT知识分享网。

1. 运行结果
   

2. 方法一：Prim算法

#include <iostream>
using namespace std;

const int INF = 0x3fffffff;
const int N = 100;
int city[N][N];  //邻接矩阵
bool used[N];    //已经经过的城市
int point[N],edge[N];   //最邻近点，以及到最邻近点的边值

void Prim(int n,int u)
{ 
   
    used[u] = true;
    for(int i=1;i<=n;i++)
    { 
   
        if(i==u)
            point[i] = 0;
        else
        { 
   
            point[i] = u;
            edge[i] = city[u][i];
            used[i] = false;
        }
    }
    int u0=u;
    for(int i=1;i<=n;i++)
    { 
   
        int temp = INF;
        for(int j=1;j<=n;j++)
        { 
   
            if(!used[j] && edge[j]<temp)
            { 
   
                u0 = j;
                temp = edge[j];
            }
        }
        if(u0 == u)
            break;
        used[u0] = true;
        for(int j=1;j<=n;j++)
        { 
   
            if(!used[j] && city[u0][j]<edge[j])
            { 
   
                edge[j] = city[u0][j];
                point[j] = u0;
            }
        }
    }
}


int main()
{ 
   
    int n,m,u,v,w;
    cout << "输入结点数n和边数m：";
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            city[i][j] = INF;

    cout << "输入结点数u，v和边值w：" << endl;
    for(int i=1;i<=m;i++)
    { 
   
        cin >> u >> v >> w;
        city[u][v] = w;
        city[v][u] = w;
    }

    cout << "输入任一结点：";
    cin >> u;
    int sum = 0;
    Prim(n,u);
    for(int i=1;i<=n;i++)
        sum += edge[i];

    cout << "最小花费是：" << sum << endl;

    return 0;
}

3. 方法二：Kruskal算法

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

const int N = 100;
struct Edge
{ 
   
    int v;
    int u;
    int w;
}e[N];
int father[N];
bool cmp(Edge a,Edge b)
{ 
   
    return a.w < b.w;
}

void Init(int n)
{ 
   
    for(int i=1;i<=n;i++)
        father[i] = i;
}
int FindFather(int i)
{ 
   
    if(i == father[i])
        return i;
    else
    { 
   
        int f = FindFather(father[i]);
        father[i] = f;
        return f;
    }
}

int Kruskal(int n,int m)
{ 
   
    int sum = 0;
    for(int i=1;i<=m;i++)
    { 
   
        int fv = FindFather(e[i].v);
        int fu = FindFather(e[i].u);
        if(fu != fv)
        { 
   
            sum += e[i].w;
            father[fv] = fu;
            n--;
            if(n == 1)
                return sum;
        }
    }
    return 0;
}

int main()
{ 
   
    int n,m;
    cout << "输入结点数n和边数m：";
    cin >> n >> m;
    cout << "输入结点数u，v和边值w：" << endl;
    for(int i=1;i<=m;i++)
    { 
   
        cin >> e[i].v >> e[i].u >> e[i].w;
    }
    sort(e+1,e+m+1,cmp);
    Init(n);
    cout << "最小花费是：" << Kruskal(n,m) << endl;

    return 0;
}