圖遍歷的演示課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：13 大小：529.50KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　計算機科學與技術系　　課程設計報告　　20 11～20 12 學年第二學期　　2011 年 6 月　　圖遍歷的演示<

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

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

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

5、無向圖，包含了圖的頂點vexnum和邊數edgenum。　　結點坐標信息：　　struct loc //結點坐標信息　　{　　int v; //結點序號

6、　　int x; //x坐標　　int y; //y坐標　　};　　邊結點數據結構：　　struct Edgenode//邊結點

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

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

9、　Edgenode *firstedge;//指向第一條關聯該結點的邊 　　}; 　　AMLGraph類：　　圖-1 AMLGraph類UML圖　　三、詳細設計和編碼<

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

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

12、　　Edgenode *p;　　visited[v]=1;//標志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、; //遞歸調用　　}　　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);//遞歸調用<

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

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

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

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

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

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

23、;//p指向表頭節(jié)點所指的鄰接點　　while(p!=NULL)//當表頭指針所指的鄰接點不為空　　{　　if(p->ivex==vi)　　{　　i

24、f(visited[p->jvex]==0)//邊節(jié)點內元素未被訪問則訪問節(jié)點內元素，并對其標記已訪問　　{　　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;//隊列的尾指針計數器加一，即后移一位　　Queue[rear]=p->jvex;</p&

26、gt;　　}　　p=p->ilink;//邊節(jié)點內元素已被訪問，指向下一鄰接點　　}　　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)建和初始化　　函數名稱：void AML_Init()　　函數功能：創(chuàng)建一張固定結點和邊數的無向圖，邊與結點的關系是從文件中讀取　　函數參數：形參為空，返回也為void　　具體代碼：</

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

32、;　　int edge[30][2];//二維數組來存儲邊的關系,30條邊和ivex，jvex邊集的兩結點　　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; //申請邊結點空間　　e->ivex=edge[k][0];

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

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

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

38、讀取存儲在文件中的各個頂點坐標信息　　函數參數：形參為空，返回值為空　　具體代碼：　　void init_location() //初始化結點的坐標信息　　{<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;　　}　　上機調試過程　　圖-2 具體的圖關系圖圖-3 存儲頂點坐標信息文件　　測試結果及其分析</b&g

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

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

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

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

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//頂點最大個數　　bool v

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

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

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

50、;　　{ 　　int data; //頂點名稱,用數字表示城市　　Edgenode *firstedge;//指向第一條關聯該結點的邊 　　}; 　　class AMLGr

51、aph 　　{ 　　private: 　　loc *l; //坐標信息指針　　Vexnode *adjmulist; //頂點數組指針 　　int vex

52、num; //定點數目 　　int edgenum; //邊數目 　　int maxnum; //頂點數最大值 　　public: 　　//構造函數　　A

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

54、;　　} 　　//析構函數　　~AMLGraph()　　{ 　　delete[]adjmulist; </

55、p>　　} 　　//定位頂點在頂點數組中的位置 　　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; 　　} 　　//構造無向圖

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

58、p>　　int edge[30][2];//二維數組來存儲邊的關系,30條邊和ivex，jvex邊集的兩結點　　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; //申請邊結點空間　　e->ivex=edge[k][0];<p&g

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

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

63、 //初始化所有結點的坐標信息　　} 　　//深度優(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])//如果未被訪問過，進行訪問DFS遍歷<b&g

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

66、p>　　Edgenode *p;　　visited[v]=1;//標志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); //遞歸調用</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);//遞歸調用

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; //建立隊列數組

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

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

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

78、;p>　　while(p!=NULL)//當表頭指針所指的鄰接點不為空　　{　　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é)點內元素已被訪問，指向下一鄰接點　　}　　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); //設置線形為寬度 3 像素的虛線<p&g

85、t;　　line(x1,y1,x2,y2);　　}　　void init_location() //初始化結點的坐標信息　　{　　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 函數修改窗口名稱

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<<"鄰接多重表結構："<<endl; 　　cout<<"\n1:長春2:哈爾濱3:呼和浩特4:北京5:沈陽6:寧夏7:太原8:石家莊9:天津

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

溫馨提示

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

圖遍歷的演示課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

圖遍歷的演示課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載