1、合肥學院計算機科學與技術系課程設計報告20 1120 12 學年第 二 學期課程 數據結構與算法課程設計名稱圖遍歷的演示學生姓名汪青松學號1004031010專業班級網絡工程1班指導教師呂剛、陳圣兵2011 年 6 月圖遍歷的演示一、問題分析和任務定義很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。試寫一個程序，演示在連通的無向圖上訪問全部結點的操作。將每個結點看做一個地名，如合肥。然后任選國內的城市，起點未合肥，忽略城市間的里程。設圖的結點20-30個，每個結點用一個編號表示(如果一個圖有n個結點，則它們的編號分別為1，2，n)。通過輸入圖的全部邊(存于數據文件中，從文件讀寫)輸入一個圖，

2、每個邊為一個數對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒。二、數據結構的選擇和概要設計城市與城市之間的關系使沒有方向的，無向圖采用鄰近多重表來實現，主要要表示無向圖中的各個結點和邊，在多重表中邊是采用兩個結點來表示的。在鄰接表中edgenode表示鄰接表中的結點類型，其中含有訪問標記mark，一條邊所依附的兩個結點的序號ivex和jvex，以及分別指向依附于ivex和jvex的頂點邊的鏈域ilink和jlink。其中，鄰接表中的表頭結點用vexnode表示，包含了頂點信息data和指向第一個邊結點的firstedge。用amlgraph表示整個無向圖，包含了

3、圖的頂點vexnum和邊數edgenum。結點坐標信息：struct loc /結點坐標信息int v; /結點序號int x; /x坐標int y; /y坐標;邊結點數據結構：struct edgenode/邊結點 int mark;/標志域，指示該邊是否被訪問過(0:沒有1:有) int ivex,jvex;/該邊關聯的兩個頂點的位置 edgenode *ilink,*jlink;/分別指向關聯這兩個頂點的下一條邊 ; 頂點結點：struct vexnode/頂點結點 int data; /頂點名稱,用數字表示城市 edgenode *firstedge;/指向第一條關聯該結點的邊 ; a

4、mlgraph類：amlgraph- *adjmulist：vexnode- vexnum：int- edgenum：int- maxnum：int+ amlgraph(num1:int,num2:int)+ amlgraph()+ locate_vex(v:int):int+ aml_init():void+ judge_edge(v1:int,v2:int):bool+ dfs_traverse():void+ dfs(v:int):void+ bfs_traverse():void+ bfs(v:int):void+ mark_unvisited():void+ display():vo

5、id圖-1 amlgraph類uml圖三、詳細設計和編碼程序主體部分主要包括兩大部分，一是遍歷算法部分；另一部分是對演示圖的處理。遍歷算法部分主要包括了，鄰接多重表構造的無向圖的初始化、深度遍歷和廣度遍歷；對演示圖的處理包括了，結點坐標信息的初始化和繪圖，運用了graphics.h庫中的繪圖函數。1、深度遍歷函數名稱： void dfs(int v) 函數功能：實現一張無向圖從一個指定結點的深度搜索遍歷，并輸出結點序號函數參數： int v 開始的結點具體代碼： void dfs(int v)/深度優先搜索遍歷(遞歸)edgenode *p;visitedv=1;/標志v已被訪問coutviv

6、ex=i)if(visitedp-jvex=0) /鄰近點未被訪問過 dline(lv.x,lv.y,lp-jvex.x,lp-jvex.y); dfs(p-jvex); /遞歸調用p=p-ilink; else if(visitedp-ivex=0) dline(lv.x,lv.y,lp-ivex.x,lp-ivex.y); dfs(p-ivex);/遞歸調用 p=p-jlink; 2、廣度遍歷函數名稱：void bfs(int v) 函數功能：實現一張無向圖從一個指定結點的廣度度搜索遍歷，并輸出結點序號；函數參數： int v開始的結點，返回參數為void具體代碼：void bfs(int

7、 v)/廣度優先搜索遍歷int i,vi;int queuemax_vertex_num,front=0,rear=0; /建立隊列數組edgenode *p;for(i=0;ivexnum;i+)/全部節點標記為未訪問visitedi=0;visitedv=1; /開始結點標記為已訪問coutv; /輸出當前訪問結點位置coutivex=vi)if(visitedp-jvex=0)/邊節點內元素未被訪問則訪問節點內元素，并對其標記已訪問visitedp-jvex=1;coutjvexjvex.x,lp-jvex.y); /繪制路徑rear=(rear+1)%max_vertex_num;/隊

8、列的尾指針計數器加一，即后移一位queuerear=p-jvex;p=p-ilink;/邊節點內元素已被訪問，指向下一鄰接點elseif(visitedp-ivex=0)visitedp-ivex=1;coutivexivex.x,lp-ivex.y); /繪制路徑 rear=(rear+1)%max_vertex_num;queuerear=p-ivex; p=p-jlink;3、圖的創建和初始化函數名稱：void aml_init()函數功能：創建一張固定結點和邊數的無向圖，邊與結點的關系是從文件中讀取函數參數：形參為空，返回也為void具體代碼： void aml_init() ifst

9、ream icin;icin.open(d:wenjian2.txt); int i,j,k;int edge302;/二維數組來存儲邊的關系,30條邊和ivex，jvex邊集的兩結點 for(i=0;iedgenum;i+)for(j=0;jedgeij;for(i=0;ivexnum;i+) /初始化頂點 adjmulisti.data=i+1; adjmulisti.firstedge=null; for(k=0;kivex=edgek0;e-jvex=edgek1;/讀入2個頂點的值e-ilink=adjmuliste-ivex.firstedge;/將頭結點的firstedge指針賦

10、給新結點的ilinkadjmuliste-ivex.firstedge=e;/將頭結點的指針指向新結點e-jlink=adjmuliste-jvex.firstedge;/將新結點的jlink指針指向其jvex結點所依附的結點adjmuliste-jvex.firstedge=e; init_location(); /初始化所有結點的坐標信息 4、初始化頂點坐標函數名稱：void init_location()函數功能：此函數為初始化頂點坐標，主要用來讀取存儲在文件中的各個頂點坐標信息函數參數：形參為空，返回值為空具體代碼： void init_location() /初始化結點的坐標信息if

11、stream icin;l=new loc20;icin.open(d:wenjian1.txt);for(int i=1;ili.vli.xli.y;4、 上機調試過程 圖-2 具體的圖關系圖 圖-3 存儲頂點坐標信息文件5、 測試結果及其分析圖-4 深度搜索遍歷結果圖-5深度搜索遍歷演示圖-6 廣度搜索遍歷演示圖-7 廣度度搜索遍歷演示六、用戶使用說明本程序采用c+語言在windows 7+vc6.0環境下編寫，主要功能是演示圖的兩種遍歷過程；程序所默認演示無向圖包括26個結點和30條邊，其中26個結點數字分別代表26個省會城市，30條邊表示他們之間的關系，具體關系如演示圖所示；進入軟件界

12、面后，首先需要輸入開始進行遍歷的城市位置（即對應的結點數字），然后再進行選擇進行圖遍歷的方式，本程序提供2種圖遍歷方式，深度優先遍歷和廣度優先遍歷，選擇遍歷方式后，遍歷結果將之間顯示在屏幕上，左邊數字為訪問的結點，右邊邊集是訪問時所經過的邊。在運行程序之前，請確保系統裝有easyx的graphicsk庫。七、參考文獻1 王昆侖，李紅. 數據結構與算法. 北京：中國鐵道出版社，2006年5月。2 編程中國：3 easyx：8、 附錄詳細代碼：graph.h#include #include #include #include /#include image.husing namespace st

13、d; #define max_vertex_num 30/頂點最大個數bool visited100; /頂點是否被訪問標志 struct loc /結點坐標信息int v; /結點序號int x; /x坐標int y; /y坐標;/鄰接多重表的存儲 struct edgenode/邊結點 int mark;/標志域，指示該邊是否被訪問過(0:沒有1:有) int ivex,jvex;/該邊關聯的兩個頂點的位置 edgenode *ilink,*jlink;/分別指向關聯這兩個頂點的下一條邊 ; struct vexnode/頂點結點 int data; /頂點名稱,用數字表示城市 edgen

14、ode *firstedge;/指向第一條關聯該結點的邊 ; class amlgraph private: loc *l; /坐標信息指針 vexnode *adjmulist; /頂點數組指針 int vexnum; /定點數目 int edgenum; /邊數目 int maxnum; /頂點數最大值 public: /構造函數 amlgraph(int num1=26,int num2=30) adjmulist=new vexnodenum1; vexnum=num1;edgenum=num2; maxnum=max_vertex_num; /析構函數 amlgraph() dele

15、teadjmulist; /定位頂點在頂點數組中的位置 int locate_vex(int v) for(int i=0;ivexnum;i+) if(adjmulisti.data)=v) return i; return -1; /構造無向圖 void aml_init() ifstream icin;icin.open(d:wenjian2.txt); int i,j,k;int edge302;/二維數組來存儲邊的關系,30條邊和ivex，jvex邊集的兩結點 for(i=0;iedgenum;i+)for(j=0;jedgeij; for(i=0;ivexnum;i+) /初始化頂

16、點 adjmulisti.data=i+1; adjmulisti.firstedge=null; for(k=0;kivex=edgek0;e-jvex=edgek1;/讀入2個頂點的值e-ilink=adjmuliste-ivex.firstedge;/將頭結點的firstedge指針賦給新結點的ilinkadjmuliste-ivex.firstedge=e;/將頭結點的指針指向新結點e-jlink=adjmuliste-jvex.firstedge;/將新結點的jlink指針指向其jvex結點所依附的結點adjmuliste-jvex.firstedge=e; init_locatio

17、n(); /初始化所有結點的坐標信息 /深度優先遍歷 void dfs_traverse() for(int i=0;ivexnum;i+) visitedi=false;/初始化所有頂點未被訪問過 for(i=0;ivexnum;i+) if(!visitedi)/如果未被訪問過，進行訪問dfs遍歷 dfs(i); coutendl; void dfs(int v)/深度優先搜索遍歷(遞歸)edgenode *p;visitedv=1;/標志v已被訪問coutvivex=i)if(visitedp-jvex=0) /鄰近點未被訪問過 dline(lv.x,lv.y,lp-jvex.x,lp-

18、jvex.y); dfs(p-jvex); /遞歸調用p=p-ilink; else if(visitedp-ivex=0) dline(lv.x,lv.y,lp-ivex.x,lp-ivex.y); dfs(p-ivex);/遞歸調用 p=p-jlink; /廣度優先遍歷 void bfs_traverse() for(int i=0;ivexnum;i+) visitedi=false; for(i=0;ivexnum;i+) if(!visitedi) bfs(i); coutendl; void bfs(int v)/廣度優先搜索遍歷int i,vi;int queuemax_vert

19、ex_num,front=0,rear=0; /建立隊列數組edgenode *p;for(i=0;ivexnum;i+)/全部節點標記為未訪問visitedi=0;visitedv=1; /開始結點標記為已訪問coutv; /輸出當前訪問結點位置coutivex=vi)if(visitedp-jvex=0)visitedp-jvex=1;coutjvexjvex.x,lp-jvex.y); rear=(rear+1)%max_vertex_num; queuerear=p-jvex;p=p-ilink;/邊節點內元素已被訪問，指向下一鄰接點elseif(visitedp-ivex=0)vis

20、itedp-ivex=1;coutivexivex.x,lp-ivex.y); rear=(rear+1)%max_vertex_num;queuerear=p-ivex; p=p-jlink; void dline(int x1,int y1,int x2,int y2) /畫線setlinestyle(ps_dash, null, 3); /設置線形為寬度 3 像素的虛線line(x1,y1,x2,y2);void init_location() /初始化結點的坐標信息ifstream icin;l=new loc20;icin.open(d:wenjian1.txt);for(int i=1;ili.vli.xli.y;void image()/繪制矢量無向圖hwnd hwnd = gethwnd();/ 使用 api 函數修改窗口名稱setwindowt