1、1、實驗?zāi)康模?）復(fù)習(xí)圖的存儲方法和圖的遍歷方法；（2）進一步掌握圖的非線性特點、遞歸特點和動態(tài)特性；（3）掌握最小生成樹的求解算法。2、實驗內(nèi)容（1）用Prim算法求最小生成樹；（2）輸入網(wǎng)的二維矩陣，輸出最小生成樹；3、實驗要求（1）分析算法思想，利用C（C+）語言完成程序設(shè)計。（2）上機調(diào)試通過實驗程序。（3）輸入數(shù)據(jù)，并求最小生成樹。（4）給出具體的算法分析，包括時間復(fù)雜度和空間復(fù)雜度等。（5）撰寫實驗報告（把輸入實驗數(shù)據(jù)及運行結(jié)果用抓圖的形式粘貼到實驗報告上）。4、實驗步驟與源程序?qū)嶒灢襟E我先從具體的問題中抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計出相應(yīng)的算法，其中，需要首先使用prim 的函數(shù)

2、將矩陣初始化，然后輸出無向圖的鄰接矩陣，再求最小生成樹的求解算法，最后，編寫主函 數(shù)，串接程序，并調(diào)試程序，得出實驗結(jié)果。源代碼#include #define inf 9999#define max 40/ prim的函數(shù)/ n個頂點，n-1條邊/初始化/頂點未加入到最小生成樹中/標(biāo)志頂點1加入U集合/形成n-1條邊的生成樹void prim(int gmax,int n)int lowcostmax,closestmax;int i,j,k,min;for(i=2;i=n;i+) lowcosti=g1i;closesti=1;lowcost1=0;for(i=2;i=n;i+)min=i

3、nf;k=0;for(j=2;j=n;j+) 的最小邊/尋找滿足邊的一個頂點在U,另一個頂點在Vif(lowcostjmin)&(lowcostj!=0)min=lowcostj;k=j；printf(%d,%d)%dt”,closestk,k,min);lowcostk=0;/頂點k加入Ufor(j=2;j=n;j+)/修改由頂點k到其他頂點邊的權(quán)值if(gkjlowcostj) lowcostj=gkj;closestj=k;printf(n)；intadjg(int gmax)/建立無向圖int n,e,i,j,k,v1,v2,weight;printf(-輸入頂點個數(shù)，邊的條數(shù):);s

4、canf(%d,%d”,&n,&e);for(i=1;i=n;i+)for(j=1;j=n;j+)gij=inf;/初始化矩陣，全部元素設(shè)為無窮大for(k=1;k=e;k+)printf(輸入第%d條邊的起點，終點，權(quán)值:,k);scanf(%d,%d,%d”,&v1,&v2,&weight);gv1v2=weight;gv2v1=weight;return(n);void prg(int gmax,int n)/輸出無向圖的鄰接矩陣int i,j；for(i=0;i=n;i+)printf(%dt”,i);for(i=1;i=n;i+)printf(n%dt”,i);for(j=1;j=n

5、;j+)printf(gij=inf)?”t:%dt”,gij);printf(n)；void main()int gmaxmax,n;n=adjg(g);printf(輸入無向圖的鄰接矩陣:n);prg(g,n);printf(最小生成樹的構(gòu)造:n);prim(g,n);5、測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）算法設(shè)計與分析實驗報告I卜數(shù)，邊的條數(shù): 邊的起點， 邊的起點， 邊的起點， 邊的起點， 邊的起點， 邊的起點， 邊的起點，終點 m的鄰接矩陣;終點 終點 終點 終點 終點 終點4 5 6 7 111112 5 33 4 4 60121 111114131215黛小生成樹的構(gòu)造：4 33 112 54 1113166、結(jié)果分析與實驗體會本次實驗是參考了范例程序，經(jīng)過自己的改寫，從而實現(xiàn)要求。先做簡單的輸出，一步步的再 做其它格式的設(shè)置。這次的實驗我們要做的是圖的存儲方法和圖的遍歷方法，要求我們掌握的是非 線性特點，遞歸特點和動態(tài)特征，最小生成樹的求解等。首先將初始化矩陣，全部元素設(shè)為無