數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)最小通信網(wǎng)需求分析要在n個(gè)城市間建立通信網(wǎng)，已知各個(gè)城市間的距離，建立的通信線路要使得這n個(gè)城市連通，而且建立的通信網(wǎng)絡(luò)代價(jià)最小（最短）。輸入:n個(gè)城市的距離關(guān)系圖，即圖的頂點(diǎn)和邊上的權(quán)值輸出:含n個(gè)城市頂點(diǎn)的最小生成樹中的邊和代價(jià)功能:建立圖的最小生成樹（4）測試數(shù)據(jù):見右圖概要設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu):用圖來描述n個(gè)城市間的關(guān)系，頂點(diǎn)為城市，邊上的權(quán)值為兩個(gè)城市的代價(jià)。用鄰接矩陣來存儲(chǔ)圖.使用算法的思想：這里用prim算法來實(shí)現(xiàn)求最小生成樹，假設(shè)G=（V，E）為待求圖，其中V為圖中所有頂點(diǎn)的集合，E為帶權(quán)圖中多有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和TE，其中集合U用于存放G的最小生成樹中的頂點(diǎn)，集合TE存放G的最小生成樹的邊。令集合U的初值為U{u1}（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)u0出發(fā)），集合TE的初值為TE={}。Prim算法的思想是，從所有u屬于U，v屬于V-U的邊中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v加入集合U中，將邊（u，v）加入集合TE中，如此不斷重復(fù)直到U=V時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合TE中包含了最小生成樹的所有邊。詳細(xì)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)詳細(xì)設(shè)計(jì):圖的鄰接矩陣描述：此處用32767代表表頭為頂點(diǎn)，矩陣的內(nèi)容點(diǎn)—權(quán)值—點(diǎn)2.算法詳細(xì)設(shè)計(jì)：在prim算法中，應(yīng)當(dāng)考慮如何有效的找出滿足條件的i∈U，j∈V-U,且權(quán)c[i][j]最小的邊（i,j）.實(shí)現(xiàn)這個(gè)目的的較簡單的辦法是設(shè)置兩個(gè)一維數(shù)組closest和lowcost。Lowsest[j]中存儲(chǔ)i∈U，j∈V-U且權(quán)值最小的邊（i,j）的權(quán)值c[i][j]，而closest[j]中存儲(chǔ)的是最小邊（i,j）的另一個(gè)斷點(diǎn)i。在prim算法執(zhí)行過程中，先找出V-U中l(wèi)owcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊（j,closest[j]），最后將j添加到U中，并對其他closest和lowcost作必要的修改，下面是對該算法的詳細(xì)說明。變量說明：Lowcost[i]若為初始的時(shí)候，表示（u0,i）的權(quán)值Closest[j]若為初始的時(shí)候，表示頂點(diǎn)j的另一端頂點(diǎn)，（Closest[j],j）2.對算法的語言描述：intPrim(GraphG,intu){ lowcost[MAXN],closest[MAXN];/*初始兩個(gè)數(shù)組，值都為無窮大 for(該圖中所有頂點(diǎn)的個(gè)數(shù))/*初始U集合和V-U集合 {closest[i]=u0;/*初始時(shí)U中只有u0點(diǎn)*/ lowcost[i]=G.Arcs[u0][i];/*U中頂點(diǎn)到V-U中頂點(diǎn)的代價(jià)*/ }/*尋找U集合中的頂點(diǎn)到V-U集合中最小權(quán)值的頂點(diǎn)，并逐步更改U集合 for(該圖中所有頂點(diǎn)個(gè)數(shù)) { /*設(shè)置一個(gè)變量為min，此值初始時(shí)為無窮大;for(頂點(diǎn)個(gè)數(shù)以j計(jì)數(shù)) if(j到u0得權(quán)值不為0且小于無窮大) { 用j到u0得權(quán)值替換掉min的值; 把j這個(gè)點(diǎn)記錄到k中 }/*更改U集合和V-U集合 把找到的U集合中頂點(diǎn)到V-U集合中最小權(quán)值設(shè)置為0，這樣就類似的把該頂點(diǎn)加到U中 for(頂點(diǎn)個(gè)數(shù)) if(j到k得權(quán)值不為0切小于點(diǎn)j到u0得權(quán)值) { 把j到u0得權(quán)值賦值給lowcost[j]中 把k賦值給closest[j] } }}調(diào)試分析調(diào)試過程中遇到的問題：在調(diào)試過程中，創(chuàng)建圖的時(shí)候沒有把頂點(diǎn)從0開始，結(jié)果總是導(dǎo)致輸出不正確；還有，我設(shè)置的創(chuàng)建的圖的格式應(yīng)該：頂點(diǎn)，頂點(diǎn)，權(quán)值，中間是以逗號(hào)隔開的，在一開始我是用空格隔開，總是導(dǎo)致錯(cuò)誤，這些錯(cuò)誤都是可以避免的算法的時(shí)空分析：算法共有四個(gè)for循環(huán)，第一個(gè)循環(huán)次數(shù)為n,第二個(gè)循環(huán)次數(shù)為n-1（這是由于初始時(shí)已經(jīng)把u0放入到U集合當(dāng)中），第三個(gè)位n，第四個(gè)為n，并且第二個(gè)和第三個(gè)，四個(gè)循環(huán)嵌套，所以循環(huán)次數(shù)的平方數(shù)量級(jí)。所以時(shí)間復(fù)雜度O(n2)。算法中用到了兩個(gè)輔助一維數(shù)組closese和lowcost，數(shù)組的大小為n，即圖的頂點(diǎn)個(gè)數(shù)，所以算法的空間復(fù)雜度為O（n）.使用說明和測試結(jié)果使用說明：(1).創(chuàng)建圖的時(shí)候，頂點(diǎn)要從0開始，有序連接的建立，并且要以逗號(hào)隔開，例如：頂點(diǎn)1，頂點(diǎn)2，權(quán)值（回車）；這樣一條邊就建立了。(2).測試數(shù)據(jù)：測試結(jié)果：心得體會(huì)雖然在課上已經(jīng)學(xué)習(xí)了prim算法，但只知道手動(dòng)的算法，具體用語言來實(shí)現(xiàn)對我來說還是有困難的，參考了教材上的程序，