最小代价生成树（数据结构）

//最小代价生成树
//prim算法(稠密图)：从与这棵树相连的边中选择最短的边，并将这条边及其所连顶点接入当前树中
void Prim(MGraph g,int v0,int &sum) {
    int lowcost[maxsize],visit[maxsize],v;//lowcost存放当前树到其他顶点的最小权值的顶点
    int min,k;
    v=v0;
    for(int i=0; i<g.n; i++) {
        lowcost[i]=g.edges[v0][i];
        visit[i]=0;
    }
    visit[v0]=1;
    sun=0;
    for(int i=0; i<g.n-1; i++) {
        min=INF;//INF是比所有权值都大的整数
        for(int j=0; j<g.n; j++) {
            if(visit[j]==0&&lowcost[j]<min) {
                min=lowcost[j];
                k=j;
            }
        }
        v=k;
        visit[k]=0;
        sum+=min;
        for(int j=0; j<g->n; j++) {
            if(visit[j]==0&&lowcost[j]>g.edges[v][j]) {
                lowcost[j]=g.edges[v][j];
            }
        }
    }
}

//Kruskal算法（稀疏矩阵）：每次找出候选边中权值最小的边，就将该边并入生成树中。
//重复此过程直到所有的边都被检测完为止
typedef struct Road {
    int a,b,w;//分别表示两个顶点和路径的权值
};
Road road[maxsize];
int v[maxsize];//表示并查集
int getRoot(int a) {
    if(a!=v[a])a=v[a];
    return a;
}
void Kruskal(MGraph g,int &sum,Road road[]) {
    int E,N;
    E=g.e;
    N=g.n;
    for(int i=0; i<N; i++)v[i]=i;
    sort(road,E);
    for(int i=0; i<E; i++) {
        int a=getRoot(road[i].a);
        int b=getRoot(road[i].b);
        if(a!=b) {
            v[a]=b;
            sum+=road[i].w;//求生成树的权值，这句并不是本算法的固定写法，也可改成其他
        }
    }
}