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

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：23 大?。?59.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

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

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　*******************　　實踐教學　　*******************　　計算機與通信學院　　2012年春季學期&

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

3、t;/p>　　指導教師： **** 　　成績： 　　目錄　　摘要3<b

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

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

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

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

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

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

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

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

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

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

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

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

16、gt;　　#define max 20 //最大頂點個數(shù)　　typedef struct //開始對鄰接表或圖進行定義　　{　　char vexs[20]; //頂點數(shù)的名稱　　Ad

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

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

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

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

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

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

23、/p>　　lowcost[i]=g[1][i]; //初始化 　　prevex[i]=1; //頂點未加入到最小生成樹中 　　} 　　lowcost[1]=0; //標志頂點1加入U集合 　　for(i=2

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

25、的一個頂點在U,另一個頂點在V的最小邊 　　if((lowcost[j]<min)&&(lowcost[j]!=0)) 　　{　　min=lowcost[j]; 　　k=j;

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

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

28、>　　printf("\n"); 　　} 　　return 0;　　} 　　int ac

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

30、gt;　　return f;　　}　　void kruscal_arc(MGraph_L G,algraph gra)　　{ 　　edg

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

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

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

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

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

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

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

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

39、<<x<<","<<y<<")"<<m;　　cout<<endl;　　}　　}<

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

41、gt;　　解決Visual C++ 6.0不正確連接的問題　　明明改動了一個文件，卻要把整個項目全部重新編譯鏈接一次。剛剛鏈接好，一運行，又提示重新編譯鏈接一次。　　這是因為出現(xiàn)了未來文件(修改時間和創(chuàng)建時間比系統(tǒng)時間晚)的緣故?？梢赃@樣處理：找到工程文件夾下的debug目錄，將創(chuàng)建和修改時間都比系統(tǒng)時間的文件全部刪除，然后再從新“

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

61、p>　　{　　cout<<"輸入頂點"<<i<<endl;　　cin>>G.vexs[i];　　fout<<G.vexs[i]<<" ";</p

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

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

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

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

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

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

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

69、gt;　　}　　}　　int visited[max];//訪問標記　　int we;　　typedef struct arcnode//弧結(jié)點</p&

70、gt;　　{　　int adjvex;//該弧指向的頂點的位置　　struct arcnode *nextarc;//弧尾相同的下一條弧　　char *info;//該弧信息　　}arcnode

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

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

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

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

75、　　queueptr front;　　queueptr rear;　　}linkqueue;　　//………………………………………………………………………　　typedef struct acr

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

91、　　void adjprint(algraph gra)　　{　　int i;　　for(i=0;i!=gra.vexnum;++i)　　{

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

124、ra,j);　　cout<<endl;　　}　　}　　return 0;　　}<

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

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

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

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

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

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

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

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

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

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

135、t;　　{　　int lowcost[max],prevex[max]; //LOWCOST[]存儲當前集合U分別到剩余結(jié)點的最短路徑　　//prevex[]存儲最短路徑在U中的結(jié)點　　int i,j,k,min;　　for(i=2;

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

偷窥国产在线91,亚洲无线国产观看原创,日本精品aⅴ一区二区三区,久久九九兔免费精品6

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

文檔簡介

溫馨提示

最新文檔

評論

偷窥国产在线91,亚洲无线国产观看原创,日本精品aⅴ一区二区三区,久久九九兔免费精品6

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載