圖遍歷的演示課程設(shè)計報告

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

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

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

文檔簡介

1、　　計算機(jī)科學(xué)與技術(shù)系　　課程設(shè)計報告　　20 11～20 12 學(xué)年第二學(xué)期　　2011 年 6 月　　圖遍歷的演示<

2、/p>　　一、問題分析和任務(wù)定義　　很多涉及圖上操作的算法都是以圖的遍歷操作為基礎(chǔ)的。試寫一個程序，演示在連通的無向圖上訪問全部結(jié)點的操作。將每個結(jié)點看做一個地名，如合肥。然后任選國內(nèi)的城市，起點未合肥，忽略城市間的里程。　　設(shè)圖的結(jié)點20-30個，每個結(jié)點用一個編號表示(如果一個圖有n個結(jié)點，則它們的編號分別為1，2，…，n

3、)。通過輸入圖的全部邊(存于數(shù)據(jù)文件中，從文件讀寫)輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒。　　二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計　　城市與城市之間的關(guān)系使沒有方向的，無向圖采用鄰近多重表來實現(xiàn)，主要要表示無向圖中的各個結(jié)點和邊，在多重表中邊是采用兩個結(jié)點來表示的。<

4、;p>　　在鄰接表中Edgenode表示鄰接表中的結(jié)點類型，其中含有訪問標(biāo)記mark，一條邊所依附的兩個結(jié)點的序號ivex和jvex，以及分別指向依附于ivex和jvex的頂點邊的鏈域ilink和jlink。　　其中，鄰接表中的表頭結(jié)點用Vexnode表示，包含了頂點信息data和指向第一個邊結(jié)點的firstedge。　　用AMLGraph表示整個

5、無向圖，包含了圖的頂點vexnum和邊數(shù)edgenum。　　結(jié)點坐標(biāo)信息：　　struct loc //結(jié)點坐標(biāo)信息　　{　　int v; //結(jié)點序號

6、　　int x; //x坐標(biāo)　　int y; //y坐標(biāo)　　};　　邊結(jié)點數(shù)據(jù)結(jié)構(gòu)：　　struct Edgenode//邊結(jié)點

7、　{ 　　int mark;//標(biāo)志域，指示該邊是否被訪問過(0:沒有1:有) 　　int ivex,jvex;//該邊關(guān)聯(lián)的兩個頂點的位置 　　Edgenode *ilink,*jlink;//分別指向關(guān)聯(lián)這兩個頂點的下一條邊

8、}; 　　頂點結(jié)點：　　struct Vexnode//頂點結(jié)點 　　{ 　　int data; //頂點名稱,用數(shù)字表示城市

9、　Edgenode *firstedge;//指向第一條關(guān)聯(lián)該結(jié)點的邊 　　}; 　　AMLGraph類：　　圖-1 AMLGraph類UML圖　　三、詳細(xì)設(shè)計和編碼<

10、;p>　　程序主體部分主要包括兩大部分，一是遍歷算法部分；另一部分是對演示圖的處理。遍歷算法部分主要包括了，鄰接多重表構(gòu)造的無向圖的初始化、深度遍歷和廣度遍歷；對演示圖的處理包括了，結(jié)點坐標(biāo)信息的初始化和繪圖，運用了graphics.h庫中的繪圖函數(shù)。　　1、深度遍歷　　函數(shù)名稱： void DFS(int v

11、) 　　函數(shù)功能：實現(xiàn)一張無向圖從一個指定結(jié)點的深度搜索遍歷，并輸出結(jié)點序號函數(shù)參數(shù)： int v 開始的結(jié)點　　具體代碼：　　void DFS(int v)//深度優(yōu)先搜索遍歷(遞歸)　　{

12、　　Edgenode *p;　　visited[v]=1;//標(biāo)志v已被訪問　　cout<<v<<" ";　　int i=v;　　p=adjmul

13、ist[v].firstedge;//取v邊表的頭指針，使P指向firstedge　　while(p!=NULL) //依次搜索v的鄰接點　　{　　if(p->ivex==i)　　{<

14、;/p>　　if(visited[p->jvex]==0) //鄰近點未被訪問過　　{ 　　dline(l[v].x,l[v].y,l[p->jvex].x,l[p->jvex].y);　　DFS(p->jvex)

15、; //遞歸調(diào)用　　}　　p=p->ilink;　　}　　else　　{</b&g

16、t;　　if(visited[p->ivex]==0)　　{　　dline(l[v].x,l[v].y,l[p->ivex].x,l[p->ivex].y);　　DFS(p->ivex);//遞歸調(diào)用<

17、/p>　　}　　p=p->jlink;　　}　　} 　　}&

18、lt;p>　　2、廣度遍歷　　函數(shù)名稱：void BFS(int v) 　　函數(shù)功能：實現(xiàn)一張無向圖從一個指定結(jié)點的廣度度搜索遍歷，并輸出結(jié)點序號；　　函數(shù)參數(shù)： int v開始的結(jié)點，返回參數(shù)為void

19、具體代碼：　　void BFS(int v)//廣度優(yōu)先搜索遍歷　　{　　int i,vi;　　int Queue[MAX_VERTEX_NUM],front=0,rear=0

20、; //建立隊列數(shù)組　　Edgenode *p;　　for(i=0;i<vexnum;i++)//全部節(jié)點標(biāo)記為未訪問　　visited[i]=0;　　visited[v]=1; //開始結(jié)點標(biāo)記為已訪問　　cout&l

21、t;<v; //輸出當(dāng)前訪問結(jié)點位置　　cout<<"\n";　　rear=(rear+1)%MAX_VERTEX_NUM; //取模初始化隊列　　Queue[rear]=v;//入隊　　while(front!=rear)/

22、/隊頭和隊尾計數(shù)器不相等，即當(dāng)隊列非空　　{　　front=(front+1)%MAX_VERTEX_NUM;//出隊　　vi=Queue[front];//vi即表頭數(shù)據(jù)元素值　　p=adjmulist[vi].firstedge

23、;//p指向表頭節(jié)點所指的鄰接點　　while(p!=NULL)//當(dāng)表頭指針?biāo)傅泥徑狱c不為空　　{　　if(p->ivex==vi)　　{　　i

24、f(visited[p->jvex]==0)//邊節(jié)點內(nèi)元素未被訪問則訪問節(jié)點內(nèi)元素，并對其標(biāo)記已訪問　　{　　visited[p->jvex]=1;　　cout<<p->jvex<<" ";</

25、p>　　dline(l[vi].x,l[vi].y,l[p->jvex].x,l[p->jvex].y); //繪制路徑　　rear=(rear+1)%MAX_VERTEX_NUM;//隊列的尾指針計數(shù)器加一，即后移一位　　Queue[rear]=p->jvex;</p&

26、gt;　　}　　p=p->ilink;//邊節(jié)點內(nèi)元素已被訪問，指向下一鄰接點　　}　　else　　{</

27、b>　　if(visited[p->ivex]==0)　　{　　visited[p->ivex]=1;　　cout<<p->ivex<<" ";

28、　　dline(l[vi].x,l[vi].y,l[p->ivex].x,l[p->ivex].y); //繪制路徑　　rear=(rear+1)%MAX_VERTEX_NUM;　　Queue[rear]=p->ivex;　　}</b

29、>　　p=p->jlink;　　}　　}　　}　　}</p&

30、gt;　　3、圖的創(chuàng)建和初始化　　函數(shù)名稱：void AML_Init()　　函數(shù)功能：創(chuàng)建一張固定結(jié)點和邊數(shù)的無向圖，邊與結(jié)點的關(guān)系是從文件中讀取　　函數(shù)參數(shù)：形參為空，返回也為void　　具體代碼：</

31、p>　　void AML_Init() 　　{ 　　ifstream icin;　　icin.open("d:\wenjian2.txt"); 　　int i,j,k;

32、;　　int edge[30][2];//二維數(shù)組來存儲邊的關(guān)系,30條邊和ivex，jvex邊集的兩結(jié)點　　for(i=0;i<edgenum;i++)　　for(j=0;j<2;j++)　　icin>>edge[i][j];<

33、p>　　for(i=0;i<vexnum;i++) //初始化頂點　　{ 　　adjmulist[i].data=i+1; 　　adjmulist[i].firstedge=NULL; 　　} <

34、/b>　　for(k=0;k<edgenum;k++)//初始化邊信息　　{ 　　Edgenode *e=new Edgenode; //申請邊結(jié)點空間　　e->ivex=edge[k][0];

35、;　　e->jvex=edge[k][1];//讀入2個頂點的值　　e->ilink=adjmulist[e->ivex].firstedge;//將頭結(jié)點的firstedge指針賦給新結(jié)點的ilink　　adjmulist[e->ivex].firstedge=e;//將頭結(jié)點的指針指向新結(jié)點<

36、;/p>　　e->jlink=adjmulist[e->jvex].firstedge;//將新結(jié)點的jlink指針指向其jvex結(jié)點所依附的結(jié)點　　adjmulist[e->jvex].firstedge=e;　　}

37、　init_location(); //初始化所有結(jié)點的坐標(biāo)信息　　} 　　4、初始化頂點坐標(biāo)　　函數(shù)名稱：void init_location()　　函數(shù)功能：此函數(shù)為初始化頂點坐標(biāo)，主要用來

38、讀取存儲在文件中的各個頂點坐標(biāo)信息　　函數(shù)參數(shù)：形參為空，返回值為空　　具體代碼：　　void init_location() //初始化結(jié)點的坐標(biāo)信息　　{<p&

39、gt;　　ifstream icin;　　l=new loc[20];　　icin.open("d:\wenjian1.txt");　　for(int i=1;i<=26;i++)　　icin>>l[i].v>>l[i]

40、.x>>l[i].y;　　}　　上機(jī)調(diào)試過程　　圖-2 具體的圖關(guān)系圖圖-3 存儲頂點坐標(biāo)信息文件　　測試結(jié)果及其分析</b&g

41、t;　　圖-4 深度搜索遍歷結(jié)果　　圖-5深度搜索遍歷演示　　圖-6 廣度搜索遍歷演示　　圖-7 廣度度搜索遍歷演示　　六、用戶使用說明　　本程序采用

42、C++語言在Windows 7+VC6.0環(huán)境下編寫，主要功能是演示圖的兩種遍歷過程；　　程序所默認(rèn)演示無向圖包括26個結(jié)點和30條邊，其中26個結(jié)點數(shù)字分別代表26個省會城市，30條邊表示他們之間的關(guān)系，具體關(guān)系如演示圖所示；　　進(jìn)入軟件界面后，首先需要輸入開始進(jìn)行遍歷的城市位置（即對應(yīng)的結(jié)點數(shù)字），然后再進(jìn)行選擇進(jìn)行圖遍歷的方式，本程序提供2種圖遍歷

43、方式，深度優(yōu)先遍歷和廣度優(yōu)先遍歷，選擇遍歷方式后，遍歷結(jié)果將之間顯示在屏幕上，左邊數(shù)字為訪問的結(jié)點，右邊邊集是訪問時所經(jīng)過的邊。　　在運行程序之前，請確保系統(tǒng)裝有Easyx的graphicsk庫。　　七、參考文獻(xiàn)　　[1] 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版

44、社，2006年5月。　　[2] 編程中國：http://bbs.bccn.net/thread-329777-1-1.html　　[3] Easyx：http://www.easyx.cn　　附錄　　詳細(xì)代碼：&

45、lt;/b>　　graph.h　　#include <graphics.h> 　　#include <conio.h>　　#include <iostream>

46、　　#include <fstream> 　　//#include "image.h"　　using namespace std; 　　#define MAX_VERTEX_NUM 30//頂點最大個數(shù)　　bool v

47、isited[100]; //頂點是否被訪問標(biāo)志 　　struct loc //結(jié)點坐標(biāo)信息　　{　　int v; //結(jié)點序號　　int x; //x坐標(biāo)　　int y; //y坐標(biāo)<

48、;/p>　　};　　//鄰接多重表的存儲 　　struct Edgenode//邊結(jié)點 　　{ 　　int mark;//標(biāo)志域，指示該邊是否被訪問過(0:沒有1:

49、有) 　　int ivex,jvex;//該邊關(guān)聯(lián)的兩個頂點的位置 　　Edgenode *ilink,*jlink;//分別指向關(guān)聯(lián)這兩個頂點的下一條邊 　　}; 　　struct Vexnode//頂點結(jié)點

50、;　　{ 　　int data; //頂點名稱,用數(shù)字表示城市　　Edgenode *firstedge;//指向第一條關(guān)聯(lián)該結(jié)點的邊 　　}; 　　class AMLGr

51、aph 　　{ 　　private: 　　loc *l; //坐標(biāo)信息指針　　Vexnode *adjmulist; //頂點數(shù)組指針 　　int vex

52、num; //定點數(shù)目 　　int edgenum; //邊數(shù)目 　　int maxnum; //頂點數(shù)最大值 　　public: 　　//構(gòu)造函數(shù)　　A

53、MLGraph(int num1=26,int num2=30)　　{ 　　adjmulist=new Vexnode[num1]; 　　vexnum=num1;edgenum=num2;　　maxnum=MAX_VERTEX_NUM

54、;　　} 　　//析構(gòu)函數(shù)　　~AMLGraph()　　{ 　　delete[]adjmulist; </

55、p>　　} 　　//定位頂點在頂點數(shù)組中的位置 　　int Locate_Vex(int v) 　　{ 　　for(int i=0;i<vexnum;i++)&l

56、t;/p>　　if((adjmulist[i].data)==v) 　　return i; 　　return -1; 　　} 　　//構(gòu)造無向圖

57、　　void AML_Init() 　　{ 　　ifstream icin;　　icin.open("d:\wenjian2.txt"); 　　int i,j,k;<

58、p>　　int edge[30][2];//二維數(shù)組來存儲邊的關(guān)系,30條邊和ivex，jvex邊集的兩結(jié)點　　for(i=0;i<edgenum;i++)　　for(j=0;j<2;j++)　　icin>>edge[i][j];　　for

59、(i=0;i<vexnum;i++) //初始化頂點　　{ 　　adjmulist[i].data=i+1; 　　adjmulist[i].firstedge=NULL; 　　} <

60、/p>　　for(k=0;k<edgenum;k++)//初始化邊信息　　{ 　　Edgenode *e=new Edgenode; //申請邊結(jié)點空間　　e->ivex=edge[k][0];<p&g

61、t;　　e->jvex=edge[k][1];//讀入2個頂點的值　　e->ilink=adjmulist[e->ivex].firstedge;//將頭結(jié)點的firstedge指針賦給新結(jié)點的ilink　　adjmulist[e->ivex].firstedge=e;//將頭結(jié)點的指針指向新結(jié)點<p

62、>　　e->jlink=adjmulist[e->jvex].firstedge;//將新結(jié)點的jlink指針指向其jvex結(jié)點所依附的結(jié)點　　adjmulist[e->jvex].firstedge=e;　　} 　　init_location();

63、 //初始化所有結(jié)點的坐標(biāo)信息　　} 　　//深度優(yōu)先遍歷 　　void DFS_Traverse() 　　{

64、for(int i=0;i<vexnum;i++) 　　visited[i]=false;//初始化所有頂點未被訪問過　　for(i=0;i<vexnum;i++) 　　if(!visited[i])//如果未被訪問過，進(jìn)行訪問DFS遍歷<b&g

65、t;　　DFS(i); 　　cout<<endl; 　　} 　　void DFS(int v)//深度優(yōu)先搜索遍歷(遞歸)　　{<

66、p>　　Edgenode *p;　　visited[v]=1;//標(biāo)志v已被訪問　　cout<<v<<" ";　　int i=v;　　p=adjmulist[v].firstedge

67、;//取v邊表的頭指針，使P指向firstedge　　while(p!=NULL) //依次搜索v的鄰接點　　{　　if(p->ivex==i)　　{<p&g

68、t;　　if(visited[p->jvex]==0) //鄰近點未被訪問過　　{ 　　dline(l[v].x,l[v].y,l[p->jvex].x,l[p->jvex].y);　　DFS(p->jvex); //遞歸調(diào)用</p

69、>　　}　　p=p->ilink;　　}　　else　　{&l

70、t;p>　　if(visited[p->ivex]==0)　　{　　dline(l[v].x,l[v].y,l[p->ivex].x,l[p->ivex].y);　　DFS(p->ivex);//遞歸調(diào)用

71、;　　}　　p=p->jlink;　　}　　} 　　}

72、;　　//廣度優(yōu)先遍歷 　　void BFS_Traverse() 　　{ 　　for(int i=0;i<vexnum;i++) 　　visited[i]=false; <p&

73、gt;　　for(i=0;i<vexnum;i++) 　　if(!visited[i]) 　　BFS(i); 　　cout<<endl; 　　} <

74、p>　　void BFS(int v)//廣度優(yōu)先搜索遍歷　　{　　int i,vi;　　int Queue[MAX_VERTEX_NUM],front=0,rear=0; //建立隊列數(shù)組

75、　　Edgenode *p;　　for(i=0;i<vexnum;i++)//全部節(jié)點標(biāo)記為未訪問　　visited[i]=0;　　visited[v]=1; //開始結(jié)點標(biāo)記為已訪問　　cout<<v; //輸出當(dāng)前訪問結(jié)點位置</p&g

76、t;　　cout<<"\n";　　rear=(rear+1)%MAX_VERTEX_NUM; //取模初始化隊列　　Queue[rear]=v;//入隊　　while(front!=rear)//隊頭和隊尾計數(shù)器不相等，即當(dāng)隊列非空

77、　　{　　front=(front+1)%MAX_VERTEX_NUM;//出隊　　vi=Queue[front];//vi即表頭數(shù)據(jù)元素值　　p=adjmulist[vi].firstedge;//p指向表頭節(jié)點所指的鄰接點<

78、;p>　　while(p!=NULL)//當(dāng)表頭指針?biāo)傅泥徑狱c不為空　　{　　if(p->ivex==vi)　　{　　if(visited[p->jvex]==0){

79、　　visited[p->jvex]=1;　　cout<<p->jvex<<" ";　　dline(l[vi].x,l[vi].y,l[p->jvex].x,l[p->jvex].y); rear=(rear+1)%MAX_VER

80、TEX_NUM; Queue[rear]=p->jvex;　　}　　p=p->ilink;//邊節(jié)點內(nèi)元素已被訪問，指向下一鄰接點　　}　　e

81、lse　　{　　if(visited[p->ivex]==0)　　{　　visited[p->ivex]=1;　　cout

82、<<p->ivex<<" ";　　dline(l[vi].x,l[vi].y,l[p->ivex].x,l[p->ivex].y); rear=(rear+1)%MAX_VERTEX_NUM;　　Queue[rear]=p->ivex;<

83、;p>　　}　　p=p->jlink;　　}　　}　　}<b

84、>　　}　　void dline(int x1,int y1,int x2,int y2) //畫線　　{　　setlinestyle(PS_DASH, NULL, 3); //設(shè)置線形為寬度 3 像素的虛線<p&g

85、t;　　line(x1,y1,x2,y2);　　}　　void init_location() //初始化結(jié)點的坐標(biāo)信息　　{　　ifstream icin;<p&

86、gt;　　l=new loc[20];　　icin.open("d:\wenjian1.txt");　　for(int i=1;i<=26;i++)　　icin>>l[i].v>>l[i].x>>l[i].y;

87、;　　}　　void image()//繪制矢量無向圖　　{　　HWND hWnd = GetHWnd();　　// 使用 API 函數(shù)修改窗口名稱

88、SetWindowText(hWnd, "圖的遍歷演示");　　HWND initgraph(　　int Width,　　int Height,　　int Flag =SHOWCONSOLE

89、;　　);　　initgraph(800, 600); 　　loadimage(NULL, "D:\\map1.bmp");　　}　　}; </p

90、>　　Main.h　　#include "graph.h" 　　#include <iostream> 　　#include <cstdlib>　　using n

91、amespace std; 　　void main() 　　{ 　　system("color f0");　　AMLGraph G; 　　G.AML_Init(); <

92、;/p>　　int v,op;　　char op1;　　cout<<"\t\t\t圖的DFS和BFS的演示V1.0\n";　　cout<<"\t\t\t正在從文件中讀取。。。\n";

93、　　cout<<"\t\t\t從文件中讀取信息完畢\n";　　//cout<<"鄰接多重表結(jié)構(gòu)："<<endl; 　　cout<<"\n1:長春2:哈爾濱3:呼和浩特4:北京5:沈陽6:寧夏7:太原8:石家莊9:天津

94、10:濟(jì)南\n11:西安12:鄭州13:南京14:上海15:合肥16:成都17:重慶18:武漢19:杭州20:貴州\n21:長沙22:南昌23:福州24:昆明25:南寧26:廣州";　　while(1){ 　　cout<<"\n\t\t\t請輸入起始位置（用地名前的數(shù)字表示）：\n";&

95、lt;p>　　cin>>v;　　cout<<"\t\t1.DFS"<<endl;　　cout<<"\t\t2.BFS"<<endl;　　cout<<"

96、;\t\t請選擇遍歷方式:";　　cin>>op;　　switch(op)　　{　　case 1:cout<<"DFS如下：\n";G.ima

97、ge();G.DFS(v);break;　　case 2:cout<<"BFS如下：\n";G.image();G.BFS(v);;break;　　}　　cout<<"\n\t\t\t是否繼續(xù)？(Y/N)";&l

98、t;/p>　　cin>>op1;　　if(op1=='N'||op1=='n')　　{　　cout<<"\t\t\t感謝使用！";b

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

溫馨提示

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

圖遍歷的演示課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

圖遍歷的演示課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載