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

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