數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-圖的遍歷.doc

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