數(shù)據(jù)結(jié)構(gòu)Kruskal算法求解最小生成樹

《數(shù)據(jù)結(jié)構(gòu)Kruskal算法求解最小生成樹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)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("圖中所有邊按權(quán)值遞增的排序如下:");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("最短路徑長(zhǎng)度為：%d",weight);}voidmain(){intvexnum,i;Edgeedge=NULL;printf("請(qǐng)輸入定點(diǎn)個(gè)數(shù)、各頂點(diǎn)和權(quán)值：輸入形式如下：nijw...-1-1-1n

13、表示圖的頂點(diǎn)個(gè)數(shù)，ijw表示從頂點(diǎn)i到頂點(diǎn)j的權(quán)為w的一條邊，均以-1結(jié)尾。");scanf("%d",&vexnum);for(i=0;i