數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-圖的遍歷和生成樹的求解實(shí)現(xiàn)說(shuō)明書

1、<p>　　*******************</p><p><b>　　實(shí)踐教學(xué)</b></p><p>　　*******************</p><p><b>　　計(jì)算機(jī)與通信學(xué)院</b></p><p><b>　　2012年春季學(xué)期</b>&

2、lt;/p><p>　　算法與數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)</p><p>　　題 目：圖的遍歷和生成樹的求解實(shí)現(xiàn) </p><p>　　專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　姓 名： *** </p><p>　　學(xué) 號(hào)： 1234567 &l

3、t;/p><p>　　指導(dǎo)教師： **** </p><p>　　成 績(jī)： </p><p><b>　　目 錄</b></p><p><b>　　摘 要3</b></p><p><b

4、>　　前 言4</b></p><p><b>　　正 文5</b></p><p><b>　　1.問(wèn)題描述：5</b></p><p>　　2.采用類c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型5</p><p>　　3．各模塊流程圖及偽碼算法6</p><p&g

5、t;　　4．函數(shù)的調(diào)用關(guān)系圖8</p><p><b>　　5．調(diào)試分析9</b></p><p>　　1.調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決方法9</p><p>　　2.算法的時(shí)間復(fù)雜度和空間復(fù)雜度9</p><p><b>　　6.測(cè)試結(jié)果10</b></p><p&

6、gt;<b>　　參考文獻(xiàn)14</b></p><p><b>　　摘 要</b></p><p>　　圖是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，一個(gè)圖G（Grah）由兩個(gè)集合V和E</p><p>　　構(gòu)成，圖存在兩種遍歷方式，深度優(yōu)先遍歷和廣度優(yōu)先遍歷，廣度優(yōu)先遍歷基本思路是假設(shè)從圖中某頂點(diǎn)U出發(fā)，在訪問(wèn)了頂點(diǎn)U之后依次訪問(wèn)U

7、的各個(gè)未訪問(wèn)的領(lǐng)接點(diǎn)，然后分別從這些領(lǐng)接點(diǎn)出發(fā)依次訪問(wèn)他們的領(lǐng)接點(diǎn)，并使先訪問(wèn)的頂點(diǎn)的領(lǐng)接點(diǎn)先于后訪問(wèn)的頂點(diǎn)被訪問(wèn)。直至所有領(lǐng)接點(diǎn)被訪問(wèn)到。深度優(yōu)先的基本思路是從某個(gè)頂點(diǎn)出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V的未被訪問(wèn)的領(lǐng)接點(diǎn)出發(fā)深度優(yōu)先檢索土。直至圖中所有頂點(diǎn)都被訪問(wèn)到。PRIM算法—KRUSKAL算法；可以對(duì)圖形進(jìn)行最小生成樹的求解。</p><p><b>　　主要問(wèn)題是：</b></p

8、><p>　?。?）當(dāng)給出一個(gè)表達(dá)式時(shí)，如何創(chuàng)建圖所表達(dá)的樹，即相應(yīng)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)？</p><p>　?。?）表達(dá)式建立好以后，如何求出其遍歷？深度優(yōu)先和廣度優(yōu)先遍歷。</p><p>　?。?）計(jì)算它的最小生成樹？主要是prim算法和kruscal算法兩種形式。</p><p><b>　　前 言</b><

9、/p><p>　　很多涉及圖的操作的算法都是以圖的遍歷操作為基礎(chǔ)，通過(guò)遍歷的演示，方便在學(xué)習(xí)中更好的理解突地遍歷的過(guò)程。</p><p>　　通過(guò)對(duì)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的演示，分別兩種遍歷的不同與其優(yōu)缺點(diǎn)。</p><p>　　我們?cè)趯?duì)一些問(wèn)題進(jìn)行求解時(shí)，會(huì)發(fā)現(xiàn)有些問(wèn)題很難找到規(guī)律，或者根本無(wú)規(guī)律可尋。對(duì)于這樣的問(wèn)題，可以利用計(jì)算機(jī)運(yùn)算速度快的特點(diǎn)，先搜索查找

10、所有可能出現(xiàn)的情況，再根據(jù)題目條件從所有可能的情況中，刪除那些不符合條件的解。</p><p>　　在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索， 本層的結(jié)點(diǎn)沒(méi)有搜索處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展， 也就是說(shuō)先產(chǎn)生 的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。很多問(wèn)題都可以用廣度優(yōu)先搜索進(jìn)行處理，如翻幣問(wèn)題、最短路徑問(wèn)題等

11、。</p><p>　　在計(jì)算機(jī)中，有多種方法存儲(chǔ)圖的信息，由于圖的結(jié)構(gòu)復(fù)雜，使用廣泛，一般應(yīng)根據(jù)實(shí)際的應(yīng)用，選擇適合的表示方法。常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接多重表和鄰接表。</p><p>　　在實(shí)際問(wèn)題當(dāng)中，經(jīng)常遇到這類問(wèn)題，為新建的某個(gè)機(jī)構(gòu)進(jìn)行選址，道路交通路線，如何走完所有路線，旅游線路等一系列問(wèn)題都涉及到圖的知識(shí)。圖是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，一個(gè)圖G（Grah）由兩個(gè)集合

12、V和E。</p><p>　　構(gòu)成，圖存在兩種遍歷方式，深度優(yōu)先遍歷和廣度優(yōu)先遍歷，廣度優(yōu)先遍歷基本思路是假設(shè)從圖中某頂點(diǎn)U出發(fā)，在訪問(wèn)了頂點(diǎn)U之后依次訪問(wèn)U的各個(gè)未訪問(wèn)的領(lǐng)接點(diǎn)，然后分別從這些領(lǐng)接點(diǎn)出發(fā)依次訪問(wèn)他們的領(lǐng)接點(diǎn)，并使先訪問(wèn)的頂點(diǎn)的領(lǐng)接點(diǎn)先于后訪問(wèn)的頂點(diǎn)被訪問(wèn)。直至所有領(lǐng)接點(diǎn)被訪問(wèn)到。深度優(yōu)先的基本思路是從某個(gè)頂點(diǎn)出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V的未被訪問(wèn)的領(lǐng)接點(diǎn)出發(fā)深度優(yōu)先檢索圖。直至圖中所有頂點(diǎn)都被

13、訪問(wèn)到。PRIM算法—KRUSKAL算法；可以對(duì)圖形進(jìn)行最小生成樹的求解。</p><p>　　樹型結(jié)構(gòu)是一種非線性結(jié)構(gòu)，它用于描述數(shù)據(jù)元素之間層次關(guān)系，如人類社會(huì)的族譜等，樹型結(jié)構(gòu)的應(yīng)用非常廣泛，磁盤文件目錄結(jié)構(gòu)就是一個(gè)典型的例子。</p><p><b>　　正 文</b></p><p><b>　　1.問(wèn)題描述：</b

14、></p><p>　　圖是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，一個(gè)圖G（Grah）由兩個(gè)集合V和E</p><p>　　構(gòu)成，圖存在兩種遍歷方式，深度優(yōu)先遍歷和廣度優(yōu)先遍歷，廣度優(yōu)先遍歷基本思路是假設(shè)從圖中某頂點(diǎn)U出發(fā)，在訪問(wèn)了頂點(diǎn)U之后依次訪問(wèn)U的各個(gè)未訪問(wèn)的領(lǐng)接點(diǎn)，然后分別從這些領(lǐng)接點(diǎn)出發(fā)依次訪問(wèn)他們的領(lǐng)接點(diǎn)，并使先訪問(wèn)的頂點(diǎn)的領(lǐng)接點(diǎn)先于后訪問(wèn)的頂點(diǎn)被訪問(wèn)。直至所有領(lǐng)接點(diǎn)被訪問(wèn)到。深度優(yōu)

15、先的基本思路是從某個(gè)頂點(diǎn)出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V的未被訪問(wèn)的領(lǐng)接點(diǎn)出發(fā)深度優(yōu)先檢索土。直至圖中所有頂點(diǎn)都被訪問(wèn)到。PRIM算法—KRUSKAL算法；可以對(duì)圖形進(jìn)行最小生成樹的求解。</p><p>　　2.采用類c語(yǔ)言定義相關(guān)的數(shù)據(jù)類型</p><p>　　#define int_max 10000 //定義鄰接矩陣最大值10000為無(wú)窮大</p><p&

16、gt;　　#define max 20 //最大頂點(diǎn)個(gè)數(shù)</p><p>　　typedef struct //開始對(duì) 鄰接表或圖進(jìn)行定義</p><p><b>　　{</b></p><p>　　char vexs[20]; //頂點(diǎn)數(shù)的名稱</p><p>　　Ad

17、jMatrix arcs; //鄰接矩陣 </p><p>　　int vexnum,arcnum //圖中頂點(diǎn)數(shù)和邊數(shù)</p><p>　　int creatMGraph_L(MGraph_L &G)//創(chuàng)建圖用鄰接矩陣表示</p><p>　　int visited[max]; //訪問(wèn)標(biāo)記</p>&

18、lt;p>　　typedef struct arcnode //弧結(jié)點(diǎn)</p><p>　　int adjvex; //該弧指向的頂點(diǎn)的位置，即邊或弧依賴的頂點(diǎn)序號(hào)</p><p>　　char *info; // 該弧信息</p><p>　　char data; //結(jié)點(diǎn)信息</p>&

19、lt;p><b>　　基本操作：</b></p><p>　　int creatadj(algraph &gra,MGraph_L G)//用鄰接表存儲(chǔ)圖</p><p>　　int initqueue(linkqueue &q)//初始化隊(duì)列</p><p>　　int enqueue(linkqueue &q,

20、int e)//入隊(duì)</p><p>　　int dequeue(linkqueue &q,int &e)//出隊(duì)</p><p>　　int queueempty(linkqueue q)//判斷隊(duì)為空</p><p>　　void bfstra(algraph gra)//廣度優(yōu)先遍歷</p><p>　　int bfst

21、ra_fen(algraph gra)//求連通分量</p><p>　　3．各模塊流程圖及偽碼算法</p><p>　　int prim(int g[][max],int n) //最小生成樹PRIM算法</p><p><b>　　{</b></p><p>　　int lowcost[max],prevex[max

22、]; //LOWCOST[]存儲(chǔ)當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑</p><p>　　//prevex[]存儲(chǔ)最短路徑在U中的結(jié)點(diǎn)</p><p>　　int i,j,k,min; </p><p>　　for(i=2;i<=n;i++) //n個(gè)頂點(diǎn)，n-1條邊 </p><p><b>　　{</b><

23、/p><p>　　lowcost[i]=g[1][i]; //初始化 </p><p>　　prevex[i]=1; //頂點(diǎn)未加入到最小生成樹中 </p><p><b>　　} </b></p><p>　　lowcost[1]=0; //標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 </p><p>　　for(i=2

24、;i<=n;i++) //形成n-1條邊的生成樹 </p><p><b>　　{</b></p><p><b>　　min=inf; </b></p><p><b>　　k=0; </b></p><p>　　for(j=2;j<=n;j++) //尋找滿足邊

25、的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 </p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0)) </p><p><b>　　{</b></p><p>　　min=lowcost[j]; </p><p><b>　　k=j; </b>

26、;</p><p><b>　　} </b></p><p>　　printf("(%d,%d)%d\t",prevex[k]-1,k-1,min); </p><p>　　lowcost[k]=0; //頂點(diǎn)k加入U(xiǎn) </p><p>　　for(j=2;j<=n;j++) //修改由頂點(diǎn)k到

27、其他頂點(diǎn)邊的權(quán)值 </p><p>　　if(g[k][j]<lowcost[j]) </p><p><b>　　{</b></p><p>　　lowcost[j]=g[k][j]; </p><p>　　prevex[j]=k; </p><p><b>　　} </b

28、></p><p>　　printf("\n"); </p><p><b>　　} </b></p><p><b>　　return 0;</b></p><p><b>　　} </b></p><p>　　int ac

29、rvisited[100];//kruscal弧標(biāo)記數(shù)組</p><p>　　int find(int acrvisited[],int f)</p><p><b>　　{</b></p><p>　　while(acrvisited[f]>0)</p><p>　　f=acrvisited[f];</p&

30、gt;<p><b>　　return f;</b></p><p><b>　　}</b></p><p>　　void kruscal_arc(MGraph_L G,algraph gra)</p><p><b>　　{ </b></p><p>　　edg

31、 edgs[20];</p><p>　　int i,j,k=0;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=i;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(G.arcs[i][j]

32、.adj!=10000)</p><p><b>　　{</b></p><p>　　edgs[k].pre=i;</p><p>　　edgs[k].bak=j;</p><p>　　edgs[k].weight=G.arcs[i][j].adj;</p><p><b>　　++k;

33、</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int x,y,m,n;</p><p>　　int buf,edf;</p><p>　　for(i=0;i!=gra.arcnum;++i)</

34、p><p>　　acrvisited[i]=0; </p><p>　　for(j=0;j!=G.arcnum;++j)</p><p><b>　　{</b></p><p><b>　　m=10000;</b></p><p>　　for(i=0;i!=G.arcnum;++

35、i)</p><p><b>　　{</b></p><p>　　if(edgs[i].weight<m)</p><p><b>　　{</b></p><p>　　m=edgs[i].weight;</p><p>　　x=edgs[i].pre;</p>

36、;<p>　　y=edgs[i].bak;</p><p><b>　　n=i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　// cout<<x<<y<<m;

37、</p><p>　　// cout<<endl;</p><p>　　buf=find(acrvisited,x);</p><p>　　edf=find(acrvisited,y); </p><p>　　// cout<<buf<<" "<<edf<&l

38、t;endl;</p><p>　　edgs[n].weight=10000;</p><p>　　if(buf!=edf)</p><p><b>　　{</b></p><p>　　acrvisited[buf]=edf;</p><p>　　cout<<"("

39、<<x<<","<<y<<")"<<m;</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><

40、;b>　　}</b></p><p>　　4．函數(shù)的調(diào)用關(guān)系圖</p><p>　　函數(shù)調(diào)用關(guān)系如圖4.1所示</p><p>　　圖4.1 函數(shù)調(diào)用關(guān)系圖</p><p><b>　　5．調(diào)試分析</b></p><p>　　1.調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決方法</p&

41、gt;<p>　　解決Visual C++ 6.0不正確連接的問(wèn)題</p><p>　　明明改動(dòng)了一個(gè)文件，卻要把整個(gè)項(xiàng)目全部重新編譯鏈接一次。剛剛鏈接好，一運(yùn)行，又提示重新編譯鏈接一次。</p><p>　　這是因?yàn)槌霈F(xiàn)了未來(lái)文件(修改時(shí)間和創(chuàng)建時(shí)間比系統(tǒng)時(shí)間晚)的緣故?？梢赃@樣處理：找到工程文件夾下的debug目錄，將創(chuàng)建和修改時(shí)間都比系統(tǒng)時(shí)間的文件全部刪除，然后再?gòu)男隆?/p>

42、Rebuild All”一次。</p><p>　　2.算法的時(shí)間復(fù)雜度和空間復(fù)雜度</p><p>　　關(guān)于時(shí)間復(fù)雜度的計(jì)算是按照運(yùn)算次數(shù)來(lái)進(jìn)行的, 關(guān)于空間復(fù)雜度的計(jì)算是在程序運(yùn)行過(guò)程所要借助的內(nèi)容空間大小。</p><p>　　即：空間復(fù)雜是儲(chǔ)存空間的大小和變換等等決定的...</p><p>　　時(shí)間復(fù)雜是邏輯比較、賦值等基本運(yùn)算的次

43、數(shù)決定的...</p><p>　　prim算法的時(shí)間復(fù)雜度為O（n 2）,kruskcal算法的時(shí)間復(fù)雜度為O（eloge）</p><p>　　prim的空間復(fù)雜度為O（n* prevex）, kruskcal算法的空間復(fù)雜度為O（n）</p><p><b>　　6.測(cè)試結(jié)果</b></p><p>　　(1）輸

44、入圖的頂點(diǎn)即弧度個(gè)數(shù)：</p><p>　　(2)分別寫出邊的權(quán)值：</p><p>　　鄰接矩陣和鄰接表創(chuàng)建成功，顯示出菜單：</p><p>　　菜單選擇：輸入0，顯示鄰接矩陣</p><p>　　輸出y 進(jìn)行下一步操作，重新選擇菜單，輸出1顯示鄰接表：</p><p>　　輸出y 進(jìn)行下一步操作，重新選擇菜單，輸

45、出2顯示廣度優(yōu)先遍歷：</p><p>　　輸出y 進(jìn)行下一步操作，重新選擇菜單，輸出3顯示深度優(yōu)先遍歷：</p><p>　　輸出y 進(jìn)行下一步操作，重新選擇菜單，輸出4，顯示prim算法計(jì)算最小生成樹：</p><p>　　輸出y 進(jìn)行下一步操作，重新選擇菜單，輸出5，顯示kruscal算法計(jì)算最小生成樹：</p><p>　　輸出y 進(jìn)

46、行下一步操作，重新選擇菜單，輸出6,計(jì)算出該圖的連通分量：</p><p>　　輸出n，結(jié)束操作，退出運(yùn)行:</p><p><b>　　設(shè)計(jì)總結(jié)</b></p><p>　　在這三周的算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中,我的題目是:圖的遍歷和生成樹的求解實(shí)現(xiàn),這三周課程設(shè)計(jì)中,通過(guò)該題目的設(shè)計(jì)過(guò)程,我加深了對(duì)圖數(shù)據(jù)結(jié)構(gòu)及隊(duì)列的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)及圖的深

47、度優(yōu)先和廣度優(yōu)先遍歷過(guò)程,Prim算法和Kruscal算法進(jìn)行最小生成樹求解過(guò)程的理解,對(duì)圖數(shù)據(jù)結(jié)構(gòu)上基本運(yùn)算的實(shí)現(xiàn)有所掌握,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力。</p><p>　　一個(gè)人要完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)中我會(huì)更加注意各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)遇到了很多的問(wèn)題，在老師的幫助，和對(duì)各種資料的查閱中，將

48、問(wèn)題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。</p><p>　　三周的課程設(shè)計(jì)很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時(shí)書本中無(wú)法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉了自己分析問(wèn)題，解決問(wèn)題的能力，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì)，組織，來(lái)配合學(xué)習(xí)，三周中我收益很 大，學(xué)到很多。</p><p><b>　　致

49、 謝</b></p><p>　　在本次算法與數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)中，我學(xué)到了很多的東西，同時(shí)也得到了很多人的幫助和指導(dǎo)。在此我非常的感謝他們，感謝他們這些天對(duì)我的幫助、感謝他們對(duì)我的悉心指導(dǎo)。</p><p>　　其次，我更要感謝我們的指導(dǎo)老師王旭陽(yáng)老師。謝謝她這三周以來(lái)對(duì)我們的悉心指導(dǎo)和幫助。感謝她能在百忙中抽出時(shí)間，在機(jī)房高溫之下還非常認(rèn)真的為我們做課設(shè)指導(dǎo)，在此，我深深

50、的感謝我的指導(dǎo)老師。</p><p>　　最后，我還要感謝我們的學(xué)校以及學(xué)校領(lǐng)導(dǎo)，感謝他們能夠給我們一個(gè)這么好的鍛煉平臺(tái)，讓我們能夠?qū)ψ约核鶎W(xué)的知識(shí)充分的利用和學(xué)習(xí)，讓我的個(gè)人能力也有所提高。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　1. 嚴(yán)蔚敏，吳偉民， 《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，北京：清華大學(xué)出版社，2003<

51、;/p><p>　　2. 嚴(yán)蔚敏，吳偉民， 《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》，北京：清華大學(xué)出版社，2005</p><p>　　3. 《DATA STRUCTURE WITH C++》，William Ford，William Tcpp，北京：清華大學(xué)出版社（影印版），2005</p><p>　　4. 譚浩強(qiáng)，《C語(yǔ)言程序設(shè)計(jì)》，北京：清華大學(xué)出版社，2005</

52、p><p>　　附錄 原程序(帶注釋)</p><p>　　#include <iostream></p><p>　　#include <malloc.h></p><p>　　#include<fstream></p><p>　　using namespace std;</p

53、><p>　　#define int_max 10000</p><p>　　#define inf 9999</p><p>　　#define max 20</p><p>　　//…………………………………………鄰接矩陣定義……………………</p><p>　　typedef struct ArcCell</p

54、><p><b>　　{</b></p><p><b>　　int adj;</b></p><p>　　char *info;</p><p>　　}ArcCell,AdjMatrix[20][20];</p><p>　　typedef struct</p>

55、<p><b>　　{</b></p><p>　　char vexs[20];</p><p>　　AdjMatrix arcs;</p><p>　　int vexnum,arcnum;</p><p>　　}MGraph_L;</p><p>　　//^^^^^^^^^^^^^^^

56、^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^</p><p>　　int localvex(MGraph_L G,char v)//返回V的位置</p><p><b>　　{</b></p><p><b>　　int i=0;</b></p><p&g

57、t;　　while(G.vexs[i]!=v)</p><p><b>　　{</b></p><p><b>　　++i;</b></p><p><b>　　}</b></p><p><b>　　return i;</b></p>&l

58、t;p><b>　　}</b></p><p>　　int creatMGraph_L(MGraph_L &G)//創(chuàng)建圖用鄰接矩陣表示"\n"括號(hào)</p><p><b>　　{</b></p><p>　　ofstream fout("out.doc",ios::o

59、ut);</p><p>　　char v1,v2;</p><p>　　int i,j,w;</p><p>　　cout<<"…………創(chuàng)建無(wú)向圖…………"<<endl<<"請(qǐng)輸入圖G頂點(diǎn)和弧的個(gè)數(shù):(5 7)不包括\"()\""<<endl;</p&

60、gt;<p>　　cin>>G.vexnum>>G.arcnum;</p><p>　　fout<<G.vexnum<<" "<<G.arcnum<<"\n";</p><p>　　for(i=0;i!=G.vexnum;++i)</p><

61、p><b>　　{</b></p><p>　　cout<<"輸入頂點(diǎn)"<<i<<endl;</p><p>　　cin>>G.vexs[i];</p><p>　　fout<<G.vexs[i]<<" ";</p

62、><p><b>　　}</b></p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　G.arcs[i][j].adj=int_ma

63、x;</p><p>　　G.arcs[i][j].info=NULL;</p><p><b>　　}</b></p><p>　　for(int k=0;k!=G.arcnum;++k)</p><p><b>　　{</b></p><p>　　cout<<

64、"輸入一條邊依附的頂點(diǎn)和權(quán):(a b 3)不包括\"()\""<<endl;</p><p>　　cin>>v1>>v2>>w;//輸入一條邊依附的兩點(diǎn)及權(quán)值</p><p>　　fout<<endl;</p><p>　　fout<<v1<<

65、" "<<v2<<" "<<w;</p><p>　　i=localvex(G,v1);//確定頂點(diǎn)V1和V2在圖中的位置</p><p>　　j=localvex(G,v2);</p><p>　　G.arcs[i][j].adj=w;</p><p>　　G

66、.arcs[j][i].adj=w;</p><p><b>　　}</b></p><p>　　cout<<"圖G鄰接矩陣創(chuàng)建成功！"<<endl;</p><p>　　fout.close();</p><p>　　return G.vexnum;</p>&

67、lt;p><b>　　}</b></p><p>　　void ljjzprint(MGraph_L G)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=G.vexnum;++i)&

68、lt;/p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;++j)</p><p>　　cout<<G.arcs[i][j].adj<<" ";</p><p>　　cout<<endl;</p><p&

69、gt;<b>　　}</b></p><p><b>　　}</b></p><p>　　int visited[max];//訪問(wèn)標(biāo)記</p><p><b>　　int we;</b></p><p>　　typedef struct arcnode//弧結(jié)點(diǎn)</p&

70、gt;<p><b>　　{</b></p><p>　　int adjvex;//該弧指向的頂點(diǎn)的位置</p><p>　　struct arcnode *nextarc;//弧尾相同的下一條弧</p><p>　　char *info;//該弧信息</p><p><b>　　}arcnode

71、;</b></p><p>　　typedef struct vnode//鄰接鏈表頂點(diǎn)頭接點(diǎn)</p><p><b>　　{</b></p><p>　　char data;//結(jié)點(diǎn)信息</p><p>　　arcnode *firstarc;//指向第一條依附該結(jié)點(diǎn)的弧的指針</p><

72、;p>　　}vnode,adjlist;</p><p>　　typedef struct//圖的定義</p><p><b>　　{</b></p><p>　　adjlist vertices[max];</p><p>　　int vexnum,arcnum;</p><p><

73、b>　　int kind;</b></p><p><b>　　}algraph;</b></p><p>　　//…………………………………………隊(duì)列定義……………………</p><p>　　typedef struct qnode</p><p><b>　　{</b><

74、/p><p><b>　　int data;</b></p><p>　　struct qnode *next;</p><p>　　}qnode,*queueptr;</p><p>　　typedef struct</p><p><b>　　{</b></p>

75、<p>　　queueptr front;</p><p>　　queueptr rear;</p><p>　　}linkqueue;</p><p>　　//………………………………………………………………………</p><p>　　typedef struct acr</p><p><b>

76、;　　{</b></p><p>　　int pre;//弧的一結(jié)點(diǎn)</p><p>　　int bak;//弧另一結(jié)點(diǎn)</p><p>　　int weight;//弧的權(quán)</p><p><b>　　}edg;</b></p><p>　　int creatadj(algraph

77、&gra,MGraph_L G)//用鄰接表存儲(chǔ)圖</p><p><b>　　{</b></p><p>　　int i=0,j=0;</p><p>　　arcnode *arc,*tem,*p;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>&

78、lt;b>　　{</b></p><p>　　gra.vertices[i].data=G.vexs[i];</p><p>　　gra.vertices[i].firstarc=NULL;</p><p><b>　　}</b></p><p>　　for(i=0;i!=G.vexnum;++i)&l

79、t;/p><p><b>　　{</b></p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(gra.vertices[i].firstarc==NULL)</p><p><b>　　

80、{</b></p><p>　　if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　arc=(arcnode *)malloc(sizeof(arcnode));</p><p>　　arc->

81、adjvex=j;</p><p>　　gra.vertices[i].firstarc=arc;</p><p>　　arc->nextarc=NULL;</p><p><b>　　p=arc;</b></p><p><b>　　++j;</b></p><p>

82、　　while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　tem=(arcnode *)malloc(sizeof(arcnode));</p><p>　　tem->adjvex=j;</p><p>

83、;　　gra.vertices[i].firstarc=tem;</p><p>　　tem->nextarc=arc;</p><p><b>　　arc=tem;</b></p><p><b>　　++j;</b></p><p><b>　　}</b></p

84、><p><b>　　--j;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></

85、p><p>　　if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)</p><p><b>　　{</b></p><p>　　arc=(arcnode *)malloc(sizeof(arcnode));</p><p>　　arc->adjvex=j;</p&

86、gt;<p>　　p->nextarc=arc;</p><p>　　arc->nextarc=NULL;</p><p><b>　　p=arc;</b></p><p><b>　　}</b></p><p><b>　　}</b></p&g

87、t;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　gra.vexnum=G.vexnum;</p><p>　　gra.arcnum=G.arcnum;</p><p>　　/*for(i=0;i!=gra.vexnum;++i)</

88、p><p><b>　　{</b></p><p>　　arcnode *p;</p><p>　　cout<<i<<" ";</p><p>　　p=gra.vertices[i].firstarc;</p><p>　　while(p!=NULL)<

89、;/p><p><b>　　{</b></p><p>　　cout<<p->adjvex;</p><p>　　p=p->nextarc;</p><p><b>　　}</b></p><p>　　cout<<endl;</p>

90、<p><b>　　}*/</b></p><p>　　cout<<"圖G鄰接表創(chuàng)建成功！"<<endl;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>

91、　　void adjprint(algraph gra)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p>

92、;<p>　　arcnode *p;</p><p>　　cout<<i<<" ";</p><p>　　p=gra.vertices[i].firstarc;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p&

93、gt;<p>　　cout<<p->adjvex;</p><p>　　p=p->nextarc;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p>&l

94、t;p><b>　　}</b></p><p>　　int firstadjvex(algraph gra,vnode v)//返回依附頂點(diǎn)V的第一個(gè)點(diǎn)</p><p>　　//即以V為尾的第一個(gè)結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　if(v.firstarc!=N

95、ULL)</p><p>　　return v.firstarc->adjvex;</p><p><b>　　}</b></p><p>　　int nextadjvex(algraph gra,vnode v,int w)//返回依附頂點(diǎn)V的相對(duì)于W的下一個(gè)頂點(diǎn)</p><p><b>　　{<

96、/b></p><p>　　arcnode *p;</p><p>　　p=v.firstarc;</p><p>　　while(p!=NULL&&p->adjvex!=w)</p><p><b>　　{</b></p><p>　　p=p->nextarc;

97、</p><p><b>　　}</b></p><p>　　if(p->adjvex==w&&p->nextarc!=NULL)</p><p><b>　　{</b></p><p>　　p=p->nextarc;</p><p>　　r

98、eturn p->adjvex;</p><p><b>　　}</b></p><p>　　if(p->adjvex==w&&p->nextarc==NULL)</p><p>　　return -10;</p><p><b>　　}</b></p>

99、<p>　　int initqueue(linkqueue &q)//初始化隊(duì)列</p><p><b>　　{</b></p><p>　　q.rear=(queueptr)malloc(sizeof(qnode));</p><p>　　q.front=q.rear;</p><p>　　if(

100、!q.front)</p><p><b>　　return 0;</b></p><p>　　q.front->next=NULL;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>

101、　　int enqueue(linkqueue &q,int e)//入隊(duì)</p><p><b>　　{</b></p><p>　　queueptr p;</p><p>　　p=(queueptr)malloc(sizeof(qnode));</p><p><b>　　if(!p)</b&

102、gt;</p><p><b>　　return 0;</b></p><p>　　p->data=e;</p><p>　　p->next=NULL;</p><p>　　q.rear->next=p;</p><p><b>　　q.rear=p;</b>

103、;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int dequeue(linkqueue &q,int &e)//出隊(duì)</p><p><b>　　{</b></p><

104、;p>　　queueptr p;</p><p>　　if(q.front==q.rear)</p><p><b>　　return 0;</b></p><p>　　p=q.front->next;</p><p>　　e=p->data;</p><p>　　q.front

105、->next=p->next;</p><p>　　if(q.rear==p)</p><p>　　q.rear=q.front;</p><p><b>　　free(p);</b></p><p><b>　　return 1;</b></p><p><

106、;b>　　}</b></p><p>　　int queueempty(linkqueue q)//判斷隊(duì)為空</p><p><b>　　{</b></p><p>　　if(q.front==q.rear)</p><p><b>　　return 1;</b></p&g

107、t;<p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void bfstra(algraph gra)//廣度優(yōu)先遍歷</p><p><b>　　{</b></p><p><b>　　int

108、i,e;</b></p><p>　　linkqueue q;</p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p>　　visited[i]=0;</p><p>　　initqueue(q);</p><p>　　for(i=0;i!=gra.vexnum;++i)&

109、lt;/p><p>　　if(!visited[i])</p><p>　　{ visited[i]=1;</p><p>　　cout<<gra.vertices[i].data;</p><p>　　enqueue(q,i);</p><p>　　while(!queueempty(q))</p>

110、;<p><b>　　{</b></p><p>　　dequeue(q,e);</p><p>　　// cout<<" "<<e<<" ";</p><p>　　for(we=firstadjvex(gra,gra.vertices[e]);we>

111、;=0;we=nextadjvex(gra,gra.vertices[e],we))</p><p><b>　　{</b></p><p>　　if(!visited[we])</p><p><b>　　{</b></p><p>　　visited[we]=1;</p><

112、p>　　cout<<gra.vertices[we].data;</p><p>　　enqueue(q,we);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&

113、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　int dfs(algraph gra,int i);//聲明DFS</p><p>　　int dfstra(algraph gra)</p><p><b>　　{</b>&

114、lt;/p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p><p>　　visited[i]=0;</p><p><b>　　}</b>

115、</p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(visited[j]==0)</p><p>　　dfs(gra,j);</p><p><b>　　}</b></p>

116、<p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int dfs(algraph gra,int i)</p><p><b>　　{</b></p><p>　　visited[i]=1;</p>

117、;<p><b>　　int we1;</b></p><p>　　// cout<<i<<visited[i]<<endl;</p><p>　　cout<<gra.vertices[i].data;</p><p>　　// cout<<endl;</p>

118、<p>　　for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))</p><p><b>　　{</b></p><p>　　// cout<<we<<visited[we]<<endl;</

119、p><p><b>　　we1=we;</b></p><p>　　// cout<<nextadjvex(gra,gra.vertices[i],we)<<endl;</p><p>　　if(visited[we]==0)</p><p>　　// cout<<</p>

120、<p>　　dfs(gra,we);//<<endl;</p><p>　　// cout<<i<<we1<<endl;</p><p><b>　　we=we1;</b></p><p>　　// cout<<nextadjvex(gra,gra.vertices[i]

121、,we)<<endl;</p><p><b>　　}</b></p><p>　　return 12;</p><p><b>　　}</b></p><p>　　int bfstra_fen(algraph gra)//求連通分量</p><p><b&

122、gt;　　{</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i!=gra.vexnum;++i)</p><p><b>　　{</b></p><p>　　visited[i]=0;</p><p><b

123、>　　}</b></p><p>　　for(j=0;j!=gra.vexnum;++j)</p><p><b>　　{</b></p><p>　　if(visited[j]==0)</p><p><b>　　{</b></p><p>　　dfs(g

124、ra,j);</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}<

125、/b></p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int adjvex;</p><p>　　int lowcost;</p><p>　　}closedge;</p><p>　　/*int min

126、imum(closedge *p);</p><p>　　int minispantree(MGraph_L G,char u)</p><p><b>　　{</b></p><p>　　int k,j,i;</p><p>　　closedge closedge_a[20];</p><p>

127、　　k=localvex(G,u);</p><p>　　// cout<<k<<endl;</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p><b>　　{</b></p><p><b>　　if(j!=k)</b></p>

128、<p><b>　　{</b></p><p>　　closedge_a[j].adjvex=u;</p><p>　　closedge_a[j].lowcost=G.arcs[k][j].adj;</p><p><b>　　}</b></p><p>　　for(i=1;i!=G.

129、vexnum;++i)</p><p><b>　　{</b></p><p>　　k=minimum(closedge_a);</p><p><b>　　cout<<k;</b></p><p>　　cout<<closedge_a[k].adjvex<<&q

130、uot; "<<G.vexs[k]<<endl;</p><p>　　closedge_a[k].lowcost=0;</p><p>　　for(j=0;j!=G.vexnum;++j)</p><p>　　if(G.arcs[k][j].adj<closedge_a[j].lowcost)</p><p

131、><b>　　{</b></p><p>　　closedge_a[j].adjvex=G.vexs[k];</p><p>　　closedge_a[j].lowcost=G.arcs[k][j].adj;</p><p><b>　　}</b></p><p><b>　　}&l

132、t;/b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int minimum(closedge *p)</p><p><b&g

133、t;　　{</b></p><p>　　int s=10000;</p><p>　　for(;p!=NULL;++p)</p><p><b>　　{</b></p><p>　　if(s>p->lowcost)</p><p>　　s=p->lowcost;<

134、;/p><p><b>　　}</b></p><p><b>　　return s;</b></p><p><b>　　}*/</b></p><p>　　int prim(int g[][max],int n) //最小生成樹PRIM算法</p><p&g

135、t;<b>　　{</b></p><p>　　int lowcost[max],prevex[max]; //LOWCOST[]存儲(chǔ)當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑</p><p>　　//prevex[]存儲(chǔ)最短路徑在U中的結(jié)點(diǎn)</p><p>　　int i,j,k,min;</p><p>　　for(i=2;

136、i<=n;i++) //n個(gè)頂點(diǎn)，n-1條邊</p><p><b>　　{</b></p><p>　　lowcost[i]=g[1][i]; //初始化</p><p>　　prevex[i]=1; //頂點(diǎn)未加入到最小生成樹中</p><p><b>　　}</b></p>

137、<p>　　lowcost[1]=0; //標(biāo)志頂點(diǎn)1加入U(xiǎn)集合</p><p>　　for(i=2;i<=n;i++) //形成n-1條邊的生成樹</p><p><b>　　{</b></p><p><b>　　min=inf;</b></p><p><b>　　

138、k=0;</b></p><p>　　for(j=2;j<=n;j++) //尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊</p><p>　　if((lowcost[j]<min)&&(lowcost[j]!=0))</p><p><b>　　{</b></p><p>　

139、　min=lowcost[j];</p><p><b>　　k=j;</b></p><p><b>　　}</b></p><p>　　printf("(%d,%d)%d\t",prevex[k]-1,k-1,min);</p><p>　　lowcost[k]=0; //頂

140、點(diǎn)k加入U(xiǎn)</p><p>　　for(j=2;j<=n;j++) //修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值</p><p>　　if(g[k][j]<lowcost[j])</p><p><b>　　{</b></p><p>　　lowcost[j]=g[k][j];</p><p>

141、　　prevex[j]=k;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p>&l

142、t;b>　　}</b></p><p>　　int acrvisited[100];//kruscal弧標(biāo)記數(shù)組</p><p>　　int find(int acrvisited[],int f)</p><p><b>　　{</b></p><p>　　while(acrvisited[f]>

143、;0)</p><p>　　f=acrvisited[f];</p><p><b>　　return f;</b></p><p><b>　　}</b></p><p>　　void kruscal_arc(MGraph_L G,algraph gra)</p><p>

144、<b>　　{</b></p><p>　　edg edgs[20];</p><p>　　int i,j,k=0;</p><p>　　for(i=0;i!=G.vexnum;++i)</p><p>　　for(j=i;j!=G.vexnum;++j)</p><p><b>　　{