问题引入 

 【问题描述】

编写程序，利用带权无向图的邻接矩阵存储，实现图的最小生成树Kruskal算法。

 

 

【输入形式】

输入图的顶点序列及图的边的情况。如样例所示。边的输入以输入-1,-1,-1作为结束。

0,1,6 表示对应的顶点及边是：A到B的边权值为6.

【输出形式】

输出图的最小生成树

【样例输入1】

ABCDEF#

0,1,6

0,2,1

0,3,5

1,2,5

1,4,3

2,4,6

2,5,4

2,3,5

3,5,2

4,5,6

-1,-1,-1

【样例输出1】

(A,C)--1

(D,F)--2

(B,E)--3

(C,F)--4

(B,C)--5

【样例输入2】

ABCDEFG#

0,1,5

0,2,4

0,3,2

0,4,6

1,6,3

2,4,1

3,5,3

4,5,5

5,6,1

-1,-1,-1

【样例输出2】

(C,E)--1

(F,G)--1

(A,D)--2

(B,G)--3

(D,F)--3

(A,C)--4

【评分标准】

在指定处补充代码，完成用Kruskal算法构造最小生成树。

程序设计 

#include<stdio.h>
#define N 20
#define TRUE 1
#define INF 32766         
#define INFIN 32767       

typedef struct{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}graph;

typedef struct{
    int begin ,end;   
    int weight;  
}Edge;

Edge edges[N];
void SortEdges(graph *g){
    int i,j,k,L=0;
    for(i=0;i<g->vexnum;i++)
        for(j=i;j<g->vexnum;j++)
        if(g->arcs[i][j]!=INF&&g->arcs[i][j]!=0)        
        {
            k=L;
            while(k>0&&edges[k-1].weight>g->arcs[i][j])            
            {
                edges[k]=edges[k-1];
                k--;
             }
            edges[k].weight=g->arcs[i][j];
            edges[k].begin=i;
            edges[k].end=j;
            L++;
        }
}

int flag[N];
void Kruskal(graph *g){
    int i,j,factor,temp;
    for(i=0;i<g->vexnum;i++){
        flag[i]=i;
    }
    for(i=0;i<g->arcnum;i++){
        if(flag[edges[i].begin]!=flag[edges[i].end]){
            printf("(%c,%c)--%d\n",g->vexs[edges[i].begin],g->vexs[edges[i].end],edges[i].weight);
            factor=flag[edges[i].begin];
            temp=flag[edges[i].end];
            for(j=0;j<g->vexnum;j++){
                if(flag[j]==temp){
                    flag[j]=factor;
                }
            }
        }
    }
}
void CreateMGraph(graph *g){
    int i,j,k;
    char v;
    scanf("%c",&v);
    i=0;
    g->arcnum=g->vexnum=0;
    while(v!='#'){
        g->vexs[i++]=v;
        scanf("%c",&v);
        g->vexnum++;
    }
    for(i=0;i<g->vexnum;i++){
        for(j=0;j<g->vexnum;j++){
            g->arcs[i][j]=INFIN;
        }
    }
    scanf("%d,%d,%d",&i,&j,&k);
    while(i!=-1){
        g->arcs[i][j]=k;
        g->arcs[j][i]=k;
        g->arcnum++;
        scanf("%d,%d,%d",&i,&j,&k);
    }
}

int main()
{
    graph ga;
    CreateMGraph(&ga);
    SortEdges(&ga);
    Kruskal(&ga);
    return 0;
}