課程設計(論文)題 目 名 稱 圖的遍歷 課 程 名 稱 數據結構課程設計 學 生 姓 名 學 號 系 、專 業 信息工程系、電子科學技術 指 導 教 師 2012年 12 月 23 日 目 錄1 前言22 需求分析22.1課程設計目的22.2課程設計任務22.3運行環境33 概要設計43.1總體設計流程43.2主函數流程圖54 詳細設計64.1實驗的基本思想和基本原理64.2圖的遍歷65 算法描述95.1圖的初始化95.2圖的遍歷106 結果與結論126.1源程序代碼127課程設計總結17參考文獻18致謝181 前言數據結構主要介紹一些最常用的數據結構，闡明各種數據結構內在的邏輯關系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現算法，并對算法的效率進行簡單的分析和討論。數據結構是介于數學、計算機軟件和計算機硬件之間的一門計算機專業的核心課程，它是計算機程序設計、數據庫、操作系統、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統工程等各種領域。2 需求分析2.1課程設計目的學習數據結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。通過此次課程設計主要達到以下目的：1.了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；2.初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；3.提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4.訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。2.2課程設計任務1.問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2.邏輯設計：對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型。邏輯設計的結果應寫出每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的功能說明)，各個主要模塊的算法；3.詳細設計：定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規格說明盡可能明確具體。詳細設計的結果是對數據結構和基本操作作出進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架并畫出模塊之間的調用關系圖；4.程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；5.程序調試與測試：采用自底向上，分模塊進行，即先調試低層函數。能夠熟練掌握調試工具的各種功能，設計測試數據確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果；2.3運行環境（1）WINDOWS 2000/2003/XP/7/Vista系統（2）Visual C+或TC集成開發環境193 概要設計3.1總體設計流程圖用戶登錄錄入圖信息進入主菜單更改數據深度優先遍歷廣度優先遍歷退出程序圖3.1 總體設計流程圖3.2主函數流程圖BeginCreatueMGraph(G)ch1=ych1=y輸入ch2CreatueMGraph(G)DFSTraverseM(G)BFSTraverseM(G)ch1=nbreakOverch2Y1N230圖3.2 主函數流程圖4 詳細設計4.1實驗的基本思想和基本原理和樹的遍歷類似，圖的遍歷也是從某個頂點出發，沿著某條搜索路徑對圖中每個頂點各做一次且僅做一次訪問。它是許多圖的算法的基礎。遍歷常用兩種方法：深度優先搜索遍歷；廣度優先搜索遍歷 4.2圖的遍歷1圖的深度優先搜索深度優先搜索是一種遞歸的過程，正如算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優先搜索中，對于最新發現的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續下去。當結點v的所有邊都己被探尋過，搜索將回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點并重復以上過程，整個進程反復進行直到所有結點都被發現為止。圖的深度優先遍歷的遞歸定義 假設給定圖4.1的初態是所有頂點均未曾訪問過。在圖中任選一頂點v為初始出發點(源點)，則深度優先遍歷可定義如下：首先訪問出發點v，并將其標記為已訪問過；然后依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。 圖的深度優先遍歷類似于樹的前序遍歷。采用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。深度優先搜索的過程 設x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發的未檢測過的邊(x，y)。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新源點，進行新的搜索過程。算法思路 :(1)、首先訪問一個頂點vi(初始點),將其標記為已訪問過(因為圖的每個頂點可能有多個前驅和后繼，所以當一個頂點被訪問以后，必須記錄它已經被訪問，以避免再次被訪問，為此設置一個輔助數組visitedn, 它的每個元素的初值均為邏輯值假（false），即為常量0，表明尚未被訪問，一旦訪問了頂點vi，就將對應元素visitedi設置為邏輯值真，即為常量1，表明vi已被訪問)。(2)、然后從vi的任一未被訪問過的鄰接點出發進行深度優先搜索遍歷，當vi所有鄰接點均被訪問過，則退回到上一個頂點vk,從vk的另一個未被訪問過的鄰接點出發進行深度優先搜索遍歷，直到退回到初始點并且沒有未被訪問過的鄰接點為止。圖4.1 (a)訪問vo, 記錄visited0=True, 從v0的一個未被訪問過的鄰接點v1出發遍歷； (b)訪問v1, visited1=True,從v1的一個未被訪問過的鄰接點v4出發遍歷； (c)訪問v4, visited4=True,從v4的一個未被訪問過的鄰接點v5出發遍歷； (d)訪問v5, visited5=True,由于v5的兩個鄰接點v1和v4都被訪問過，退回上一鄰接點v4，又v4的兩個鄰接點v1和v5都被訪問過，再退回上一鄰接點v1,從未被訪問過鄰接點V6出發遍歷； (e)訪問v6, visited6=True,從v6的一個未被訪問過的鄰接點v2出發遍歷； (f)訪問v2, visited2=True,v2所有鄰接點都訪問過，退回上一頂點v6,同理，v6退回v1,v1退回v0,再從v0未被訪問過鄰接點v3出發遍歷；(g)訪問v3, visited3=True，退回v0,因所有鄰接點都訪問過，再退回，結束。2圖的廣度優先搜索廣度優先搜索算法（又稱寬度優先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。廣度優先搜索的基本思想首先訪問圖4.2中指定的起始點Vi并將其標記為已訪問過，然后由Vi出發訪問與它相鄰接的所有頂點Vj、 Vk，并均標記為已訪問過，然后再按照Vj、Vk的次序，訪問每一個頂點的所有未被訪問過的鄰接頂點，并均標記為已訪問過，下一步再從這些頂點出發訪問與它們相鄰接的尚未被訪問的頂點，如此做下去，直到所有的頂點均被訪問過為止在廣度優先搜索中，若對頂點V1的訪問先于頂點V2的訪問，則對V1鄰接頂點的訪問也先于V2鄰接頂點的訪問。就是說廣度優先搜索中對鄰接點的尋找具有“先進先出”的特性。因此，為了保證訪問頂點的這種先后關系，需借助一個隊列暫存那些剛訪問過的頂點。設此隊列由一個一維數組構成，數組名為Queue，隊首指針和隊尾指針分別為front和rear。假設數組足夠大，不必考慮有溢出的可能性。廣度優先搜索不是遞歸過程，不能用遞歸形式。圖4.2遍歷過程(1)訪問v0,visited0=True (2)訪問v0所有未訪問過鄰接v1和v2, visited1=True, visited2=True;(3)訪問v1所有未被訪問過的鄰接點v3和v4,v5,并將它們標記已訪問過；(4)訪問v2所有未被訪問過的鄰接點v6, visited6=True；(5)訪問v3所有未被訪問過的鄰接點v7, visited7=True；(6)訪問v4所有未被訪問過的鄰接點(無)(7)訪問v5所有未被訪問過的鄰接點v8, visited8=True；(8)訪問v6所有未被訪問過的鄰接點(無)；(9)依次訪問v7，v8所有未被訪問過的鄰接點(無)，結束。5 算法描述5.1圖的初始化1定義圖typedef struct node /*邊表結點*/ int adjvex; /*鄰接點域*/ struct node *next; /*鏈域*/EdgeNode;typedef struct vnode /*頂點表結點*/ char vertex; /*頂點域*/ EdgeNode *firstedge; /*邊表頭指針*/VertexNode;typedef VertexNode AdjListMaxVertexNum; /*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中當前頂點數和邊數*/ ALGraph; /*圖類型*/2建立圖的鄰接表void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /*定義邊表結點*/ printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /*讀入頂點數和邊數*/ scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /*建立邊表*/ scanf(%c,&a); G-adjlisti.vertex=a; /*讀入頂點信息*/ G-adjlisti.firstedge=NULL; /*邊表置為空表*/ printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /*建立邊表*/ scanf(%d%d,&i,&j); /*讀入邊（Vi，Vj）的頂點對序號*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); /*/生成邊表結點*/ s-adjvex=j; /*鄰接點序號為j*/ s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /*將新結點*S插入頂點Vi的邊表頭部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /*鄰接點序號為i*/ s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /*將新結點*S插入頂點Vj的邊表頭部*/ 5.2圖的遍歷1圖的深度優先搜索算法#define MAXVEX 100void dfs(adjlist g，int v,int n) /*從頂點v出發進行深度優先遍歷*/ struct vexnode *stackMAXVEX, *p; int visitedMAXVEX,top=0; for(i=1;i0|p!=NULL) while(p!=NULL) if (visitedp-adjvex=1) p=p-next; else printf(“%d”,p-adjvex); visitedp-adjvex=1; top+; stacktop=p; p=gp-adjvex.link; if(top0) top-; /*退棧，回溯查找已被訪問結點的未被訪問過的鄰接點 */ p=stacktop; p =p-next; 時間復雜性一個有n個頂點、e條邊的圖，在深度優先搜索圖的過程中，找鄰接點所需時間為O(e)。對輔助數組初始化時間為O(n)。因此，當用鄰接表作為圖的存儲結構時，深度優先搜索圖的時間復雜性為O(e+n)。2圖的廣度優先搜索算法void BFSM(MGraph *G，int k) 以vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索 int i，j； CirQueue Q； InitQueue(&Q)； printf(visit vertex：c，G-vexsk)； /訪問源點vk visitedk=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q) i=DeQueue(&Q)； /vi出隊 for(j=0;jn;j+)/依次搜索vi的鄰接點vj if(G-edgesij=1&!visitedj)/vi未訪問 printf(visit vertex：c，G-vexsj)；/訪問vi visitedj=TRUE； EnQueue(&Q，j)；/訪問過的vi人隊 /endwhile /BFSM6 結果與結論6.1源程序代碼#includestdio.h#includestdlib.h#define MaxVertexNum 50 /*定義最大頂點數*/typedef struct node /*邊表結點*/ int adjvex; /*鄰接點域*/ struct node *next; /*鏈域*/EdgeNode;typedef struct vnode /*頂點表結點*/ char vertex; /*頂點域*/ EdgeNode *firstedge; /*邊表頭指針*/VertexNode;typedef VertexNode AdjListMaxVertexNum; /*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中當前頂點數和邊數*/ ALGraph; /*圖類型*/* 建立圖的鄰接表 */void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /*定義邊表結點*/ printf(Input VertexNum(n) and EdgesNum(e): ); scanf(%d,%d,&G-n,&G-e); /*讀入頂點數和邊數*/ scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) /*建立邊表*/ scanf(%c,&a); G-adjlisti.vertex=a; /*讀入頂點信息*/ G-adjlisti.firstedge=NULL; /*邊表置為空表*/ printf(Input edges,Creat Adjacency Listn); for(k=0;ke;k+) /*建立邊表*/ scanf(%d%d,&i,&j); /*讀入邊（Vi，Vj）的頂點對序號*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); /*/生成邊表結點*/ s-adjvex=j; /*鄰接點序號為j*/ s-next=G-adjlisti.firstedge; G-adjlisti.firstedge=s; /*將新結點*S插入頂點Vi的邊表頭部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode); s-adjvex=i; /*鄰接點序號為i*/ s-next=G-adjlistj.firstedge; G-adjlistj.firstedge=s; /*將新結點*S插入頂點Vj的邊表頭部*/ /* 定義標志向量，為全局變量 */typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/* DFS：深度優先遍歷的遞歸算法 */void DFSM(ALGraph *G,int i) EdgeNode *p; printf(%c ,G-adjlisti.vertex); /*訪問頂點Vi*/ visitedi=TRUE; /*標記Vi已訪問*/ p=G-adjlisti.firstedge; /*取Vi邊表的頭指針*/ while(p) /*依次搜索Vi的鄰接點Vj，這里j=p-adjvex*/ if(! visitedp-adjvex) /*若Vj尚未被訪問*/ DFSM(G,p-adjvex); /*則以Vj為出發點向縱深搜索*/ p=p-next; /*找Vi的下一個鄰接點*/ void DFS(ALGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; /*標志向量初始化*/ for(i=0;in;i+) if(!visitedi) /*Vi未訪問過*/ DFSM(G,i); /*以Vi為源點開始DFS搜索*/* BFS：廣度優先遍歷 */void BFS(ALGraph *G,int k) /*以Vk為源點對用鄰接鏈表表示的圖G進行廣度優先搜索*/ int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /*定義FIFO隊列*/ for(i=0;in;i+) visitedi=FALSE; /*標志向量初始化*/ for(i=0;in;i+) cqi=-1; /*初始化標志向量*/ printf(%c ,G-adjlistk.vertex); /*訪問源點Vk*/ visitedk=TRUE; cqr=k; /*Vk已訪問，將其入隊。注意，實際上是將其序號入隊*/ while(cqf!=-1) / 隊列非空則執行 i=cqf; f=f+1; /*Vi出隊*/ p=G-adjlisti.firstedge; /*取Vi的邊表頭指針*/ while(p) /*依次搜索Vi的鄰接點Vj（令p-adjvex=j）*/ if(!visitedp-a