使用MFSet集合及克鲁斯卡尔算法实现最小生成树，但是最后结果总不对，求大神指教！

Question

#include "stdafx.h"
#include "stdafx.h"
#include
#include

#define MAX_SIZE 100 //树的最大结点数
#define MAX_VEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 190 //最大边数
//边集
typedef struct
{
char begin;

char end;

int weight;
}Edge;
//图结构
typedef struct{
Edge edge[MAX_EDGE_NUM];
char vex[MAX_VEX_NUM];
int vexnum,edgenum;
}Graph;
//树的节点结构
typedef struct Node{
char data;
int parent;
}Node;
//树的双亲表示存储结构
typedef struct{
Node node[MAX_SIZE];
int n; //结点数
}PTree,MFSet;
//初始化MFSet集合
void initMFSet(MFSet *S,Graph G){
if(!S) exit(0);
for(int i=0;i S->node[i].data=G.vex[i];
S->node[i].parent=-1;
}
S->n=G.vexnum;
}

int find_mfset(MFSet S,int i){
if(iS.n) exit(0);
int j;
for(j=i;S.node[j].parent>0;j=S.node[j].parent);
return j;
}
//合并
void merge(MFSet *S,int i,int j){
if(iS->n||jS->n) exit(0);
S->node[j].parent=i;
}
//创建无向网
void creatGraph(Graph *G){
printf("请输入定点元素个数以及边数:");
scanf("%d,%d",&G->vexnum,&G->edgenum);
if(G->edgenum>MAX_EDGE_NUM||G->vexnum>MAX_VEX_NUM){
printf("输入错误，请重新输入：");
scanf("%d,%d",&G->vexnum,&G->edgenum);
}
printf("请输入各个定点信息：\n");
for(int i=0;ivexnum;i++){
fflush(stdin);
scanf("%c",&G->vex[i]);
}
printf("请输入每条边的两个定点和权值:\n");
for(int i=0;iedgenum/2;i++){
fflush(stdin);
scanf("%c,%c,%d",&G->edge[i].begin,&G->edge[i].end,&G->edge[i].weight);
// G->edge[i].weight = rand()%100;

}
for(int i=G->edgenum/2;i<G->edgenum;i++){
    G->edge[i].begin=G->edge[i-G->edgenum/2].end;
    G->edge[i].end=G->edge[i-G->edgenum/2].begin;
    G->edge[i].weight=G->edge[i-G->edgenum/2].weight;
}

}
//找到网中某一结点元素在顶点数组中的位置
int vexLocate(Graph G,char c){
for(int i=0;i<G.vexnum;i++){
if(c==G.vex[i])
return i;
}
return -1;
}

void minSpanTree(Graph *G){
int parent[MAX_VEX_NUM];
int m,n,temp;
char a,b;
for(int i=0;ivexnum;i++){
parent[i]=0;
}
MFSet S;
initMFSet(&S,*G);

//使用冒泡排序法将边集的权值按从小到大排序
for(int i=0;i<G->edgenum;i++){
    for(int j=0;j<G->edgenum-i-1;j++){
        if(G->edge[j].weight>G->edge[j+1].weight){
            a=G->edge[j].begin;
            b=G->edge[j].end;
            temp=G->edge[j].weight;
            G->edge[j].begin=G->edge[j+1].begin;
            G->edge[j].end=G->edge[j+1].end;
            G->edge[j].weight=G->edge[j+1].weight;
            G->edge[j+1].begin=a;
            G->edge[j+1].end=b;
            G->edge[j+1].weight=temp;
        }
    }
}

for(int i=0;i<G->edgenum;i++){

    m=find_mfset(S,vexLocate(*G,G->edge[i].begin));
    n=find_mfset(S,vexLocate(*G,G->edge[i].end));
    if(m!=n){  //说明没有形成回路
        merge(&S,m,n);
        printf("<%c,%c>,%d\t",G->edge[i].begin,G->edge[i].end,G->edge[i].weight);
    }
}

}

int _tmain(int argc, _TCHAR* argv[])
{
Graph G;
creatGraph(&G);
minSpanTree(&G);
system("pause");
return 0;

}

Answer 1

http://wenku.baidu.com/link?url=vmV3WIuV75jHe9I1QQ_bm5J45lYfYU9FAhcqWs_ovvO7Ygqzs0-hfZD-19u8LZQgk3GCrRdeXRwG-LQhZggTaxbsSDo4r1OKzNNl11WO8f3