最小生成樹(shù)的Kruskal算法實(shí)驗(yàn)報(bào)告

大連民族學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：最小生成樹(shù)的Kruskal算法課程名稱(chēng)：離散數(shù)學(xué)實(shí)驗(yàn)類(lèi)型：□演示性□驗(yàn)證性□操作性■設(shè)計(jì)性□綜合性專(zhuān)業(yè)：軟件工程班級(jí)：111學(xué)生姓名：xx學(xué)號(hào)：xx實(shí)驗(yàn)日期：2012年12月6-28日實(shí)驗(yàn)地點(diǎn)：金石灘校區(qū)機(jī)房201實(shí)驗(yàn)學(xué)時(shí)：10學(xué)時(shí)實(shí)驗(yàn)成績(jī)：指導(dǎo)教師：焉德軍姜楠2012年12月28日[實(shí)驗(yàn)原理]設(shè)所給定無(wú)向連通加權(quán)圖具有n個(gè)結(jié)點(diǎn)，m條邊，首先，將各條邊的權(quán)按從小到大的順序排序。然后依次將這些邊按所給圖的結(jié)構(gòu)放到生成樹(shù)中去。如果在放置某一條邊時(shí)，使得生成樹(shù)形成回路，那么刪除這條邊。這樣，直至生成樹(shù)具有n-1條邊時(shí)，我們所得到的就是一棵最小生成樹(shù)。[實(shí)驗(yàn)內(nèi)容]給定無(wú)向連通加權(quán)圖，編程設(shè)計(jì)求出其一棵最小生成樹(shù)。[實(shí)驗(yàn)?zāi)康腯通過(guò)算法設(shè)計(jì)并編程實(shí)現(xiàn)求出給定無(wú)向連通加權(quán)圖的一棵最小生成樹(shù)，加深學(xué)生對(duì)求最小生成樹(shù)的Kruskal算法的理解。[實(shí)驗(yàn)步驟]邊依小到大順序得l1，l2，…，lm。置初值：S，0i，1j。假設(shè)i=n-1，那么轉(zhuǎn)〔6〕。假設(shè)生成樹(shù)邊集S并入一條新的邊lj之后產(chǎn)生的回路，那么j+1j，并轉(zhuǎn)〔4〕。否那么，i+1i；ljS〔i〕；j+1j，轉(zhuǎn)〔3〕。輸出最小生成樹(shù)S。結(jié)束。具體程序的C++實(shí)現(xiàn)如下：#include<iostream>usingnamespacestd;constintMaxVertex=20;constintMaxEdge=100;constintMaxSize=100;structEdgeType{intfrom;intto;intweight;};structEdgeGraph{charvertex[MaxVertex]; EdgeTypeedge[MaxEdge];intvertexNum;intedgeNum;};intFindRoot(intparent[],intv);voidInputInfo();voidKruskal(EdgeGraphG){intvex1,vex2,f,t;inti,num;intparent[MaxVertex];for(i=0;i<G.vertexNum;i++) { parent[i]=-1; }for(num=0,i=0;i<G.edgeNum;i++) { vex1=FindRoot(parent,G.edge[i].from); vex2=FindRoot(parent,G.edge[i].to);if(vex1!=vex2) { cout<<"("<<G.edge[i].from<<","<<G.edge[i].to<<")"<<endl; f=G.edge[i].from; t=G.edge[i].to; cout<<"("<<G.vertex[f]<<","<<G.vertex[t]<<")"<<"Weight:"<<G.edge[i].weight<<endl;cout<<endl; parent[vex2]=vex1;num++;if(num==G.vertexNum-1)return; } }return;}intFindRoot(intparent[],intv){intt; t=v;if(parent[t]>-1) { t=parent[t];}returnt;}voidInputInfo(){ EdgeGraphG; cout<<"PleaseinputvertexNum,edgeNum:"<<endl; cin>>G.vertexNum>>G.edgeNum; cout<<"Pleaseinputtheinformationofedges:"<<endl;for(inti=0;i<G.vertexNum;i++) { cin>>G.vertex[i]; } cout<<"Pleaseinputthisedgeattachestwoverticessubscriptanditsweight"<<endl;for(intj=0;j<G.edgeNum;j++) { cin>>G.edge[j].from>>G.edge[j].to>>G.edge[j].weight; } Kruskal(G);}intmain(){ InputInfo(); system("pause");return0;}實(shí)驗(yàn)過(guò)程中遇到的問(wèn)題及解決過(guò)程比方不知道如何存儲(chǔ)邊集數(shù)組，以及比知道如何聲明一些變量，函數(shù)和怎樣去調(diào)用Kruskal函數(shù)……解決：通過(guò)設(shè)置結(jié)構(gòu)體EdgeType與結(jié)構(gòu)體EdgeGraph的聯(lián)合來(lái)存儲(chǔ)邊集，因?yàn)樵趧傞_(kāi)始我在主函數(shù)中用EdgeGraph聲明變量G，來(lái)作為形參去調(diào)用Kruskal(G)，編譯時(shí)就會(huì)警告未被初始化的G，的程序出錯(cuò)，后來(lái)我將Kruskal(G)在InputInfo()中調(diào)用，因?yàn)镮nputInfo()函數(shù)中聲明了變量G，并使得G初始化，從而是的程序能正常運(yùn)行。測(cè)試的圖與預(yù)期生成的最小樹(shù)[實(shí)驗(yàn)記錄](méi)實(shí)驗(yàn)總結(jié)，感想通過(guò)這次的上機(jī)實(shí)驗(yàn)，加深了我對(duì)課本上的理論知識(shí)的認(rèn)識(shí)與理解，然我真實(shí)的體驗(yàn)到了從研究問(wèn)題到解決問(wèn)