两种方法求最小生成树

Prim算法

#include <iostream>
#include <cstring>
using namespace std;
#define MAXLEN 28
const int INF = 0x7fffffff;
int graph[MAXLEN][MAXLEN], minDis[MAXLEN];
bool visited[MAXLEN];
int n;
void prim() {
    int sum = 0;
    memset(visited,false,sizeof(visited));
    minDis[0] = 0;
    visited[0] = true;
    // 初始化各个点到最小生成树点集，即初始点的距离
    for(int i = 1; i < n;i++)
        minDis[i] = graph[0][i] == 0 ? INF : graph[0][i];
    // 循环 n-1 次即可
    for(int i = 1;i < n;i++){
        int u = -1,minD = INF;
        for(int j = 0;j < n;j++){
            // 找出连接两个集合中最短边的点
            if(!visited[j] && minD > minDis[j]){
                u = j;
                minD = minDis[j];
            }
        }
        sum += minD;
        visited[u] = true;
        for(int j = 0;j< n;j++){
            if(!visited[j] && graph[u][j] != 0 && graph[u][j] < minDis[j]){
                // 更新该点到最小生成树点集的距离
                minDis[j] = graph[u][j];
            }
        }
    }
    cout<< sum <<endl;
}

Kruskal算法（配合并查集）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int path[102], parent[102];
int n, edgeNum;
typedef struct villageEdge{
    int u;
    int v;
    int dist;
};
villageEdge villages[5202];
bool myCmp(villageEdge a, villageEdge b){
    return a.dist < b.dist;
}
int getParent(int son) {
    int p = parent[son];
    if (p == 0) parent[son] = son;
    else if (p != son) parent[son] = getParent(p);
    return parent[son];
}
void MST(){
    int uParent, vParent, sum = 0;
    for(int i = 0;i < edgeNum;i++){
        uParent = getParent(villages[i].u);
        vParent = getParent(villages[i].v);
        if(vParent != uParent){
            sum += villages[i].dist;
            if(path[uParent] < path[vParent]){
                parent[uParent] = vParent;
                path[vParent]++;
            }else{
                parent[vParent] = uParent;
                path[uParent]++;
            }
        }
    }
    printf("%d\n",sum);
}