两个最小生成树算法前者适合稠密，后者适合稀疏，都是基于邻接矩阵的算法

Prim算法

#define INF 32767
void Prim(MGraph g,int v) {
    int lowcost[MAXV];
    int min;
    int closest[MAXV],i,j,k;
    for(i=0; i<g.n; i++) {
        lowcost[i]=g.edges[v][i];
        closest[i]=v;
    }
    for(i=1; i<g.n; i++) {
        min=INF;
        for(j=0; j<g.n; j++)
            if(lowcost[j]!=0 && lowcost[j]<min) {
                min=lowcost[j];
                k=j;
            }
            printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
            lowcost[k]=0;
            for(j=0; j<g.n; j++)
                if(g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j]) {
                    lowcost[j]=g.edges[k][j];
                    closest[j]=k;
                }
            }
        }

Kruskal算法

#define MAXE 100
struct EdgeType {
    int u;
    int v;
    int w;
};
void InsertSort(EdgeType E[],int n) {
    int i,j;
    EdgeType temp;
    for(i=1; i<n; i++) {
        temp=E[i];
        j=i-1;
        while(j>=0 && temp.w<E[j].w) {
            E[j+1]=E[j];
            j--;
        }
        E[j+1]=temp;
    }
}
void Kruskal(MGraph g) {
    EdgeType E[MAXE];
    int i,j,m1,m2,sn1,sn2,k;
    int vset[MAXV];
    k=0;
    for(i=0; i<g.n; i++)
        for(j=0; j<g.n; j++)
            if(g.edges[i][j]!=0 && g.edges[i][j]!=INF) {
                E[k].u=i;
                E[k].v=j;
                E[k].w=g.edges[i][j];
                k++;
            }
            InsertSort(E,g.e);
            for(i=0; i<g.n; i++)
                vset[i]=i;
            k=1;
            j=0;
            while(k<g.n) {
                m1=E[j].u;
                m2=E[j].v;
                sn1=vset[m1];
                sn2=vset[m2];
                if(sn1!=sn2) {
                    printf(" 边(%d,%d):%d\n",m1,m2,E[j].w);
                    k++;
                    for(i=0; i<g.n; i++)
                        if(vset[i]==sn2)
                            vset[i]=sn1;
                    }
                    j++;
                }
            }