kruskal算法求最小生成樹

《kruskal算法求最小生成樹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、kruskal算法求最小生成樹課題：用kruskal算法求最小生成樹。編譯工具：VisualStudio2017kruskal算法基本思想：先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)、而邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹上的根結(jié)點(diǎn)，之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有n-1條邊為止。691044271481184e1e2e3e7e5e6e4問題：按如下連通

2、圖用kruskal算法求最小生成樹。程序源碼：#include#includeusingnamespacestd;constintN=100;intnodeset[N];intn,m;structEdge{//定義結(jié)構(gòu)體.intu;intv;intw;}e[N*N];boolcomp(Edgex,Edgey){//配合sort()方法對(duì)權(quán)值進(jìn)行升序。returnx.w

3、]=i;}intMerge(inta,intb)//將e[i].u結(jié)點(diǎn)傳遞給a;e[i].v結(jié)點(diǎn)傳遞給b.{intp=nodeset[a];//p為a結(jié)點(diǎn)的集結(jié)號(hào)，intq=nodeset[b];//q為b結(jié)點(diǎn)的集結(jié)號(hào).if(p==q)return0;//判斷結(jié)點(diǎn)間是否回環(huán)。若兩個(gè)結(jié)點(diǎn)的集結(jié)號(hào)相同，則不操作，直接返回。for(inti=1;i<=n;i++)//若兩個(gè)結(jié)點(diǎn)的集結(jié)號(hào)不相同，檢查所有結(jié)點(diǎn)，把集合號(hào)是q的改為p.{if(nodeset[i]==q)nodeset[i]=p;}return1;}intKruskal(intn){intans

4、=0;for(inti=1;i<=m;i++)if(Merge(e[i].u,e[i].v)){cout<<"A結(jié)點(diǎn)："<B結(jié)點(diǎn)："<>n>>m;Init(n);cout<<"輸入結(jié)點(diǎn)數(shù)(u),(v)和權(quán)值(w)："<>e[i].u>>e

5、[i].v>>e[i].w;sort(e+1,e+m+1,comp);intans=Kruskal(n);cout<<"最小的花費(fèi)是："<

6、4510e[11]2611e[12]2714(4)調(diào)用kruskal(n)方法，(n=7,m=12)。for(inti=1;i<=m;i++)if(Merge(e[i].u,e[i].v))//調(diào)用intMerge(inta,intb)方法{cout<<"A結(jié)點(diǎn)："<B結(jié)點(diǎn)："<

7、p為a結(jié)點(diǎn)的集結(jié)號(hào)，intq=nodeset[b];//q為b結(jié)點(diǎn)的集結(jié)號(hào).if(p==q)return0;//判斷結(jié)點(diǎn)間是否回環(huán)。若兩個(gè)結(jié)點(diǎn)的集結(jié)號(hào)相同，則不操作，直接返回。for(inti=1;i<=n;i++)//若兩個(gè)結(jié)點(diǎn)的集結(jié)號(hào)不相同，檢查所有結(jié)點(diǎn)，把集合號(hào)是q的改為p.{if(nodeset[i]==q)nodeset[i]=p;}return1;}(5)示意圖分析abnodeset[a]nodeset[b]pq373737121212353535563636573333673333161313231111341414nodeset[i

8、]ansn12345632611345632+4511343632+4+4411343332+4+4+43回環(huán)，直接返回回