数据结构Kruskal算法求解最小生成树

《数据结构Kruskal算法求解最小生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构Kruskal算法求解最小生成树#include#include#include#defineMAX100structNode{intvertex1;intvertex2;intweight;structNode*next;};typedefstructNode*Edge;Edgehead=NULL;intvisited[MAX];Edgeread(){intv1,v2,w;EdgenewNode=NULL,pointer=NULL;while

2、(1){scanf("%d%d%d",&v1,&v2,&w);if(v1==-1

3、

4、v2==-1

5、

6、w==-1)break;newNode=(Edge)malloc(sizeof(structNode));newNode->vertex1=v1;newNode->vertex2=v2;newNode->weight=w;newNode->next=NULL;pointer=head;if(pointer==NULL)head=newNode;else{if(newNode->weightw

7、eight){newNode->next=pointer;head=newNode;}else{while(pointer!=NULL&&pointer->next!=NULL){if(pointer->weightweight&&newNode->weightnext->weight){newNode->next=pointer->next;pointer->next=newNode;break;}pointer=pointer->next;}pointer->nex

8、t=newNode;}}}returnhead;}voidprintLink(Edgeedge){Edgepointer=edge;printf("图中所有边按权值递增的排序如下:");while(pointer!=NULL){printf("[%d%d]",pointer->vertex1,pointer->vertex2);printf("(%d)",pointer->weight);if(pointer->next!=NULL)printf("==>");pointer=pointer->n

9、ext;}printf("");}voidkruskal(Edgeedge,intvexnum){intvisitedEdgeNum=0,weight=0;printf("最小生成树的路径为:");while(visitedEdgeNumvertex1]==0

10、

11、visited[edge->vertex2]==0){printf("[%d%d]",edge->vertex1,edge->vertex2);printf("(%d)",edge->w

12、eight);weight+=edge->weight;visitedEdgeNum++;visited[edge->vertex1]=1;visited[edge->vertex2]=1;}edge=edge->next;if(edge==NULL){break;}}printf("最短路径长度为：%d",weight);}voidmain(){intvexnum,i;Edgeedge=NULL;printf("请输入定点个数、各顶点和权值：输入形式如下：nijw...-1-1-1n

13、表示图的顶点个数，ijw表示从顶点i到顶点j的权为w的一条边，均以-1结尾。");scanf("%d",&vexnum);for(i=0;i