zuixiaoshengchengshu.rar_克鲁斯卡尔_最小 生成树 问题

#include <stdio.h> #include<iostream.h> #define MAX_VERTEX_NUM 10 //图的顶点数，应由用户定义 #define INFINITY 1000 /*设无穷大为1000*/ typedef struct Edge { int weight; }Edge, EdgeMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //连通网的带权邻接矩阵,作为kruskal算法的输入 typedef struct MGraph //存放G的最小生成树，作为Prim算法的输出 { EdgeMatrix edges; int vexnum; int edgenum; }MGraph; typedef struct VexGroup { int vertex; int group; }VexGroup; typedef struct EdgeMuster { int tail; //边的起点和终点 int head; int weight; //边上的权 bool used; }EdgeMuster; void InitializeMG(MGraph &G) { G.edgenum = G.vexnum = 0; for(int i = 0; i < MAX_VERTEX_NUM; ++i) for(int j = 0; j < MAX_VERTEX_NUM; ++j) G.edges[i][j].weight = INFINITY; } void CreateGraph(MGraph &G) { int i,j,s,judge=1; G.edgenum=100; cout<<"请输入顶点数"<<endl; cin>>s; G.vexnum = s; while(judge){ cout<<"请输入2个顶点的编号，用空格格开:"<<endl; cin>>i>>j; cout<<"请输入以上2个顶点之间的权值"; cin>>G.edges[i-1][j-1].weight; G.edges[j-1][i-1].weight=G.edges[i-1][j-1].weight; cout<<"是否继续?(0-f,1-t)"; cin>>judge; } for(int m=1;m<=s;m++) cout<<"\tv"<<m; cout<<endl; for(i = 0; i < G.vexnum; ++i) { cout<<"\n\nv"<<i+1<<"\t"; for(j = 0; j < G.vexnum; ++j) cout<< G.edges[i][j].weight<<"\t"; } } void InitializeEVG(MGraph G, EdgeMuster E[], VexGroup VG[]) { int i, j, k = 0; for(i = 0; i < G.vexnum; ++i) { VG[i].vertex=VG[i].group = i; for(j=0; j < i; ++j) if(G.edges[i][j].weight != INFINITY) { E[k].head=j+1; E[k].tail=i+1; E[k].weight=G.edges[i][j].weight; E[k++].used= false; /*标明已经被选用了*/ } } } int GetMinIndex(MGraph G,EdgeMuster E[],VexGroup VG[]) { int i,min_index=-1, min=INFINITY; //表示图不连通,不能求MST for(i=0; i<G.edgenum; ++i) { if(!E[i].used && VG[E[i].head].group!=VG[E[i].tail].group && E[i].weight < min) { min_index = i; min=E[i].weight; } } return min_index; } void MiniSpanTree_Kruskal(MGraph G) { int i, j, k; EdgeMuster *E =new EdgeMuster[G.edgenum]; VexGroup *VG =new VexGroup[G.vexnum]; InitializeEVG(G, E, VG); cout<<"\n\nThe Minimal-Span-Tree is composed of following edges:\nedge\t\tWeight\n"; for(i=1; i<G.vexnum;++i) { k=GetMinIndex(G,E,VG); E[k].used=true; for(j=0; j<G.vexnum; ++j) { if(VG[j].group==VG[E[k].head].group) VG[j].group=VG[E[k].tail].group; } cout<<"<"<<E[k].head<<","<<E[k].tail<< ">\t\t"<< E[k]. weight <<endl; } } void main() { MGraph G; InitializeMG(G); CreateGraph(G); MiniSpanTree_Kruskal(G); }