圖的遍歷的實(shí)現(xiàn)課程設(shè)計(jì)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上學(xué) 號(hào)： 課 程 設(shè) 計(jì)題 目圖的遍歷的實(shí)現(xiàn)學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程班 級(jí)姓 名指導(dǎo)教師2013年12月23日 課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 專業(yè)班級(jí)： 指導(dǎo)教師： 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 圖的遍歷的實(shí)現(xiàn)初始條件：理論：學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課程，掌握了一種計(jì)算機(jī)高級(jí)語(yǔ)言。實(shí)踐：計(jì)算機(jī)技術(shù)系實(shí)驗(yàn)中心提供計(jì)算機(jī)及軟件開(kāi)發(fā)環(huán)境。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）1、系統(tǒng)應(yīng)具備的功能：1)先任意創(chuàng)建一個(gè)圖；2)圖的DFS,BFS的遞歸或非遞歸算法的實(shí)現(xiàn)3)要求用有向圖或無(wú)向圖分別實(shí)現(xiàn)4)要求用鄰接矩陣、鄰

2、接表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫(xiě)課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字（中文和英文）；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、有關(guān)技術(shù)的討論、設(shè)計(jì)體會(huì)等；（4）結(jié)束語(yǔ)；（5）參考文獻(xiàn)。時(shí)間安排： 2013年12月16日-25日12月19日 查閱資料12月20日 系統(tǒng)設(shè)計(jì)12月21日-22日 編程并上機(jī)調(diào)試12月23日 撰寫(xiě)報(bào)告12月24日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書(shū) 指導(dǎo)教師簽名： 2013年12月14日系主任（或責(zé)任教師）簽名： 年 月 日?qǐng)D的遍歷的實(shí)現(xiàn)摘要 本課程設(shè)計(jì)主要目的在于更深一步的了解圖的遍歷的問(wèn)題，

3、圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)，用有向圖和無(wú)向圖分別實(shí)現(xiàn)圖的遍歷，廣度優(yōu)先遍歷和深度優(yōu)先遍歷的實(shí)現(xiàn)，用鄰接矩陣和鄰接表等多種結(jié)構(gòu)存儲(chǔ)存儲(chǔ)圖。在課程設(shè)計(jì)中，程序設(shè)計(jì)設(shè)計(jì)語(yǔ)言采用Visual C，程序運(yùn)行平臺(tái)為Windows 98/2000/XP。在程序設(shè)計(jì)中我主要是解決的是給出一個(gè)圖如何用多種方法完成圖的遍歷的問(wèn)題，也包括如何創(chuàng)建一個(gè)圖，深度優(yōu)先遍歷和廣度優(yōu)先遍歷一個(gè)圖，遞歸和非遞歸的方法實(shí)現(xiàn)圖的遍歷。程序最終通過(guò)調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)。關(guān)鍵詞 程序設(shè)計(jì)；數(shù)據(jù)結(jié)構(gòu)；有向圖；無(wú)向圖；存儲(chǔ)結(jié)構(gòu)；鄰接矩陣；遞歸算法Abstract The purpose of this course

4、 design is to further understand the problem of graph traversal, figure DFS and BFS recursive and non-recursive algorithms of implementation, using directed graph and undirected graph, graph traversal is implemented, breadth-first traversal and the realization of the depth-first traversal, using adj

5、acency matrix and adjacency list and so on the many kinds of structure to store.In curriculum design, using Visual C programming design language, application platform for Windows XP / 98/2000.In programming is given a figure I mainly solve how to use a variety of methods to complete graph traversal

6、problems, including how to create a figure, depth-first traversal and breadth-first traversal a figure, the method of recursive and non-recursive traversal graph.Program debugging and running, ultimately through preliminary design goal is realized. Keywords program design;Data structure;Directed gra

7、ph;Undirected graph.Storage structure;Adjacency matrix目錄1.引 言 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，是一門理論性強(qiáng)、思維抽象、難度較大的課程。在軟件工程專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。通過(guò)本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問(wèn)題的能力。我認(rèn)為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問(wèn)題的能力。對(duì)于現(xiàn)實(shí)世界中的問(wèn)題，我們應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)

8、算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問(wèn)題的解答。 圖是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)結(jié)構(gòu)中也占著相當(dāng)大的比重。這個(gè)學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程中，我們學(xué)習(xí)了很多圖的存儲(chǔ)結(jié)構(gòu)，有鄰接矩陣、鄰接表、十字鏈表等。其中鄰接矩陣和鄰接表為圖的主要存儲(chǔ)結(jié)構(gòu)。圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)是把圖的邊信息存儲(chǔ)在一個(gè)矩陣中，是一種靜態(tài)存儲(chǔ)方法。圖的鄰接表存儲(chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法。從空間性能上說(shuō)，圖越稀疏鄰接表的空間效率相應(yīng)的越高。從時(shí)間性能上來(lái)說(shuō)，鄰接表在圖的算法中時(shí)間代價(jià)較鄰接矩陣要低。 本課程設(shè)計(jì)主要是實(shí)現(xiàn)使用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)圖，并在所

9、存儲(chǔ)的圖中實(shí)現(xiàn)深度優(yōu)先和廣度優(yōu)先遍歷以及其鏈表結(jié)構(gòu)的輸出。 2. 需求分析2.1 原理當(dāng)圖比較稀疏時(shí)，鄰接表存儲(chǔ)是最佳的選擇。并且在存儲(chǔ)圖的時(shí)候鄰接表要比鄰接矩陣節(jié)省時(shí)間。在圖存儲(chǔ)在系統(tǒng)中后，我們有時(shí)還需要對(duì)圖進(jìn)行一些操作，如需要添加一個(gè)頂點(diǎn)，修改一個(gè)頂點(diǎn)，或者刪除一個(gè)頂點(diǎn)，而這些操作都需要一圖的深度優(yōu)先及廣度優(yōu)先遍歷為基礎(chǔ)。本系統(tǒng)將構(gòu)建一個(gè)圖，圖的結(jié)點(diǎn)存儲(chǔ)的是int型數(shù)據(jù)。運(yùn)行本系統(tǒng)可對(duì)該圖進(jìn)行鏈?zhǔn)浇Y(jié)構(gòu)輸出、深度優(yōu)先及廣度優(yōu)先遍歷。控制方法如下： 表2-1 控制鍵的功能 控制鍵 1 2 3 功能 廣度優(yōu) 先遍歷 深度優(yōu) 先遍歷 退出 程序 2.2要求 (1)先任意創(chuàng)建一個(gè)圖； (2)圖的DF

10、S,BFS的遞歸或非遞歸算法的實(shí)現(xiàn) (3)要求用有向圖或無(wú)向圖分別實(shí)現(xiàn) (4)要求用鄰接矩陣、鄰接表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)2.3 運(yùn)行環(huán)境 (1)WINDOWS 7系統(tǒng) (2)C+ 編譯環(huán)境2.4 開(kāi)發(fā)工具C+語(yǔ)言3.數(shù)據(jù)結(jié)構(gòu)分析本課程設(shè)計(jì)是針對(duì)于圖的，程序中采用鄰接表進(jìn)行數(shù)據(jù)存儲(chǔ)。在計(jì)算機(jī)科學(xué)中，鄰接表 描述一種緊密相關(guān)的數(shù)據(jù)結(jié)構(gòu)，用于表征圖。在 鄰接表的表示中，對(duì)于圖中的每個(gè)頂點(diǎn)，我們將保存所有其它與之相連的頂點(diǎn)（即 “鄰接表”）。 鄰接表是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法，該存儲(chǔ)方式在圖比較稀疏是相對(duì)于圖的鄰接矩陣存儲(chǔ)有明顯優(yōu)勢(shì)。設(shè)計(jì)實(shí)現(xiàn)了圖的鄰接表結(jié)構(gòu)輸出、深度有新遍歷和廣度優(yōu)先遍歷操

11、作的實(shí)現(xiàn)。 3.1鄰接表的結(jié)構(gòu)：（1） 、頭結(jié)點(diǎn)結(jié)構(gòu)firstarcdata Firstarc：結(jié)點(diǎn)的指針域（2） 、鄰接點(diǎn)的結(jié)構(gòu)nextarcadjvex Adjvex：鄰接點(diǎn)的數(shù)據(jù)域； Nextarc：鄰接點(diǎn)的指針域，指向下一個(gè)鄰接點(diǎn)；在該程序中，除了鄰接表結(jié)構(gòu)以外，還有到了一個(gè)mark數(shù)組，它是用來(lái)標(biāo)記結(jié)點(diǎn)Vi是否被訪問(wèn)。若Vi被訪問(wèn)，則marki=1，否則為0；它是一個(gè)比較簡(jiǎn)單的一維數(shù)組。（注：在每次對(duì)圖進(jìn)行遍歷之前mark都會(huì)被清零）3.2圖的深度優(yōu)先訪問(wèn)： 從圖中每個(gè)頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V的未訪問(wèn)鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至所有與V有通路的頂點(diǎn)被訪問(wèn)，否則選擇另外未

12、訪問(wèn)點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程。3.3圖的廣度優(yōu)先遍歷： 從圖中每個(gè)頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次訪問(wèn)V的 未訪問(wèn)鄰接點(diǎn)，并保證先被訪問(wèn)的結(jié)點(diǎn)的鄰接點(diǎn)先于后被訪問(wèn)的結(jié)點(diǎn)，直至所有與V有通路的頂點(diǎn)被訪問(wèn)，否則選擇另外未訪問(wèn)點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程。4. 算法設(shè)計(jì)4.1結(jié)構(gòu)體定義及函數(shù)的聲明（1）首先，要定義頭文件，在頭文件中定義鄰接點(diǎn)point、圖的基本結(jié)點(diǎn)graph以及在廣度優(yōu)先搜索中會(huì)用到隊(duì)列queue。具體如下：struct point int n; /鄰接點(diǎn)的序號(hào)point *next; /指向下一條弧節(jié)點(diǎn)的地址;struct graphint data; /表接點(diǎn)的數(shù)據(jù)struct p

13、oint *f; /結(jié)點(diǎn)的指針域，給出自該結(jié)點(diǎn)發(fā)出的第 一弧節(jié)點(diǎn)的地址;struct queueint elemd; /隊(duì)列的容量int front; /front為首指針，指向第一個(gè)元素int rear; /rear為最后一個(gè)元素，指向隊(duì)尾元素的下一個(gè)位置q; 其次，在頭文件中還需定義鄰接表存儲(chǔ)結(jié)構(gòu)下圖的抽象數(shù)據(jù)類型定義。 （2）編寫(xiě)源文件，進(jìn)行圖的初始化，首先要輸入頂點(diǎn)信息，初始化頂點(diǎn)表，在輸入點(diǎn)v的值時(shí)，同時(shí)構(gòu)造v的鄰接點(diǎn)。輸入鄰接點(diǎn)的序號(hào)，最后生成一個(gè)鄰接點(diǎn)鏈表。子函數(shù)功能：1.void creatgraph(int m) /n表示節(jié)點(diǎn)的個(gè)數(shù) 構(gòu)造圖的鏈表結(jié)構(gòu)，在此函數(shù)中要輸入圖結(jié)點(diǎn)的

14、值，鄰接點(diǎn)的序號(hào)。2.void print(struct graph a,int m) 將圖a的鏈表結(jié)構(gòu)打印出來(lái),m為結(jié)點(diǎn)個(gè)數(shù)3.void dpv(struct graph a,int v) 對(duì)圖進(jìn)行深度優(yōu)先遍歷。先訪問(wèn)指定的頂點(diǎn)v，從該頂點(diǎn)的未被訪問(wèn)的鄰接點(diǎn)中選取一個(gè)頂點(diǎn)p,從p出發(fā)進(jìn)行深度優(yōu)先遍歷。重復(fù)以上的步驟，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。4.void wdv(struct graph a,int v,queue &Q) 從v點(diǎn)開(kāi)始廣度優(yōu)先遍歷a是連通圖或是連通分量），先訪問(wèn)頂點(diǎn)v，依次訪問(wèn)v的各個(gè)未被訪問(wèn)的鄰接點(diǎn)v1,v2,vk,分別從,v1,v2,vk出發(fā)依次

15、訪問(wèn)它們未被訪問(wèn)的鄰接點(diǎn)，并使“先被訪問(wèn)頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)”被訪問(wèn)，直至圖中所有與頂點(diǎn)v有路徑相通的頂點(diǎn)都被訪問(wèn)到。5.void enqueue(queue &Q,int e) e入隊(duì)列Q的隊(duì)尾。 6.void delqueue(queue &Q,int &e) 刪除隊(duì)列Q的對(duì)首元素。7.int queueempty(queue &Q) 判斷隊(duì)列Q是否為空。（3）編寫(xiě)主函數(shù)。用數(shù)組存放圖結(jié)點(diǎn)。輸入所要進(jìn)行的操作的序號(hào)，并設(shè)置每次只能選擇一種功能，調(diào)用相應(yīng)的函數(shù)，輸出相應(yīng)的結(jié)果。4.2 主要模塊的算法描述（1）、深度優(yōu)先遍歷算法，利用遞歸void

16、dpv(graph a,vtxptr v0) /從點(diǎn)v開(kāi)始進(jìn)行深度訪問(wèn) /a為連通圖或非連通圖的一個(gè)連通分量visit（v0）； /訪問(wèn)v結(jié)點(diǎn)markv0=1; /標(biāo)記為已訪問(wèn) w=v0的第一個(gè)鄰接點(diǎn)；while(當(dāng)鄰接點(diǎn)w存在時(shí)1)if(w未訪問(wèn))dpv(a,w);w=下一個(gè)鄰接點(diǎn)；/dpv（2）、廣度優(yōu)先遍歷算法，利用隊(duì)列先入先出void wdv(graph a,vtxptr v)/從v點(diǎn)開(kāi)始廣度優(yōu)先，a是連通圖或是連通分量visit（v）； /訪問(wèn)點(diǎn)vmarkv=1; /并標(biāo)記為以訪問(wèn) initqueue（Q)；enqueue(Q,v);/v進(jìn)隊(duì)列while(!queueempty(Q)

17、delqueue(Q,v1);w=v1的第一個(gè)鄰接點(diǎn)；while(當(dāng)鄰接點(diǎn)w存在時(shí))if(w為訪問(wèn))visit（w）； markw=1; enqueue(Q,w);w=下一個(gè)鄰接點(diǎn)； /wdv4.3 函數(shù)調(diào)用圖5. 程序?qū)崿F(xiàn)及測(cè)試5.1 創(chuàng)建工程并建立文件（1）啟動(dòng)Microsoft Visual C+ 6.0。（2）新建工程名為“課程設(shè)計(jì)” 的Win32控制臺(tái)應(yīng)用程序。（3）建立頭文件“鄰接表.cpp”，在其中定義圖的創(chuàng)建函數(shù)creategraph()、深度優(yōu)先遍歷的函數(shù)dpv()、廣度優(yōu)先遍歷的函數(shù)wdv()、輸出函數(shù)print（）以及main（），通過(guò)main （4）調(diào)用其他函數(shù)來(lái)實(shí)現(xiàn)對(duì)

18、圖的操作。6. 心得體會(huì)通過(guò)這次課程設(shè)計(jì)，我受益頗多：首先，上課時(shí)聽(tīng)的理論知識(shí)，似乎很容易接受，以及各種算法都能夠比較輕松的理解，但是在真正的運(yùn)用過(guò)程中，并不能把理論知道很好的和實(shí)踐結(jié)合起來(lái)。感覺(jué)自己有點(diǎn)眼高手低，有些知識(shí)點(diǎn)的應(yīng)用只有在實(shí)踐中才能慢慢體會(huì)，在平時(shí)做實(shí)驗(yàn)時(shí)，總感到有些無(wú)從下手。因此，在學(xué)知識(shí)的過(guò)程中，一定要多動(dòng)手、動(dòng)腦，將所學(xué)的知識(shí)熟練掌握，自如運(yùn)用。其次，通過(guò)這次課程設(shè)計(jì)，對(duì)我的邏輯思維能力是一個(gè)很大的鍛煉，再有，它還加強(qiáng)了我的系統(tǒng)思考問(wèn)題的能力，在編程方面，我開(kāi)始從整體的角度來(lái)考慮問(wèn)題了，而不再像以前一樣的，胡亂動(dòng)手。也就是因?yàn)橄惹暗倪@種編程習(xí)慣，使得我在課程設(shè)計(jì)過(guò)程中浪費(fèi)了

19、不少的時(shí)間，嘗到了教訓(xùn)。通過(guò)這次課程設(shè)計(jì)，我學(xué)習(xí)了很多平時(shí)很少關(guān)注的知識(shí)點(diǎn)，比如循環(huán)鏈，遞歸的應(yīng)用，也增強(qiáng)了自己的實(shí)踐能力和編寫(xiě)程序的能力。圖是一種較為復(fù)雜且重要的數(shù)據(jù)結(jié)構(gòu)，其特殊性在于圖形結(jié)構(gòu)中結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。用鄰接矩陣作為圖的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)很好地解決了圖的結(jié)構(gòu)難點(diǎn)， 借助于鄰接矩陣容易判定任意兩個(gè)頂點(diǎn)之間是否有邊(或弧)相連，并容易求得各個(gè)頂點(diǎn)的度。該程序通俗易懂且實(shí)用性強(qiáng)，并且該程序清單詳細(xì)具體、全面、具有很強(qiáng)的可讀性；系統(tǒng)整體上比較完美，可以從鍵盤獲取輸入元素，并且可以根據(jù)用戶輸入進(jìn)行選擇性地輸出；整體輸出畫(huà)面效果整潔、大方。 7.結(jié)束語(yǔ)

20、 經(jīng)過(guò)幾天的努力，黃天不負(fù)苦心人，我的課程設(shè)計(jì)終于完成了。本課程設(shè)計(jì)主要運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)和C+程序設(shè)計(jì)完成了用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)對(duì)圖的操作。該系統(tǒng)的主要功能為：圖的鏈?zhǔn)浇Y(jié)構(gòu)輸出、深度優(yōu)先遍歷、廣度優(yōu)先遍歷。 在這次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)中，曾遇到過(guò)一些問(wèn)題，但是經(jīng)過(guò)查找資料都已經(jīng)得到解決，也正是因?yàn)檫@些問(wèn)題引發(fā)的思考給我?guī)Я耸斋@。所以我認(rèn)為只要我們有耐心和信心，我們一定能解決問(wèn)題。再次對(duì)給過(guò)我?guī)椭乃型瑢W(xué)和各位指導(dǎo)老師表示忠心的感謝！沒(méi)有你們的幫助我想我是不能這么好的完成這項(xiàng)工作的。參考文獻(xiàn)1 嚴(yán)蔚敏、吳偉民著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.-北京清華大學(xué)出版社2 譚浩強(qiáng)著， C程序設(shè)計(jì)，-3版，-北京

21、：清華大學(xué)出版社3 薛超英著.數(shù)據(jù)結(jié)構(gòu)（第二版）用Pascal語(yǔ)言、C+語(yǔ)言對(duì)照描述算法. -武漢：華中科技大學(xué)出版社4 李陶深、趙文靜著. 面向?qū)ο蟪绦蛟O(shè)計(jì)與方法. -武漢：武漢理工大學(xué)出版社附源程序清單和運(yùn)行結(jié)果 / 程序名稱：TUDEBIANLI.C/ 程序功能：采用遞歸和非遞歸算法，有向圖和無(wú)向圖，鄰接矩陣和鄰接表等多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)圖的遍歷。#include"stdio.h"#include"stdlib.h"#define INFINITY 32767 #define MAX_VEX 20 /最大頂點(diǎn)個(gè)數(shù) #define QUEUE_

22、SIZE (MAX_VEX+1) /隊(duì)列長(zhǎng)度 bool *visited;/訪問(wèn)標(biāo)志數(shù)組 int z=1; /圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu) typedef struct char *vexs; /頂點(diǎn)向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) Graph; class Queue /隊(duì)列類 public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; re

23、ar=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; int *base; int front; int rear; ; int Locate(Graph G,char c) /圖G中查找元素c的位置for(int i=0;i<G.vexnum;i+) if(G.vexsi=c) return i; return -1; void CreateUDN(Graph &G) /創(chuàng)建無(wú)向網(wǎng)int i,j,w,s1,s2; char a,b,c,temp; pri

24、ntf("輸入頂點(diǎn)數(shù)和弧數(shù):"); scanf("%d%d",&G.vexnum,&G.arcnum); temp=getchar(); /接收回車 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配頂點(diǎn)數(shù)目 printf("輸入%d個(gè)頂點(diǎn).n",G.vexnum); for(i=0;i<G.vexnum;i+) /初始化頂點(diǎn) scanf("%c",&G.vexsi); temp=getchar(); /接收回車 for(i=0;i<

25、G.vexnum;i+) /初始化鄰接矩陣 for(j=0;j<G.vexnum;j+) G.arcsij=INFINITY; printf("輸入%d條弧.n",G.arcnum); for(i=0;i<G.arcnum;i+) /初始化弧 printf("輸入弧%d: ",i);scanf("%c %c %d%c",&a,&b,&w,&c); /輸入一條邊依附的頂點(diǎn)和權(quán)值 s1=Locate(G,a); s2=Locate(G,b); G.arcss1s2=G.arcss2s1=w; i

26、nt FirstVex(Graph G,int k) /圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn)if(k>=0 && k<G.vexnum) /k合理 for(int i=0;i<G.vexnum;i+) if(G.arcski!=INFINITY) return i; return -1; /圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)int NextVex(Graph G,int i,int j)if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) /i,j合理

27、 for(int k=j+1;k<G.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; /深度優(yōu)先遍歷 void DFS(Graph G,int k) int i; if(k=-1) /第一次執(zhí)行DFS時(shí),k為-1 for(i=0;i<G.vexnum;i+) if(!visitedi) DFS(G,i); /對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS else visitedk=true;if(z=1)printf("%c",G.vexsk);else printf(" -> %c",G.v

28、exsk); +z;/訪問(wèn)第k個(gè)頂點(diǎn) if(z-1)%G.vexnum=0) z=1;for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /對(duì)k的尚未訪問(wèn)的鄰接頂點(diǎn)i遞歸調(diào)用DFS /廣度優(yōu)先遍歷 void BFS(Graph G) int k; Queue Q; /輔助隊(duì)列Q Q.InitQueue(); for(int i=0;i<G.vexnum;i+) if(!visitedi) /i尚未訪問(wèn) visitedi=true; printf("%c ",G.vexsi); Q.EnQueue(i); /i入列 while(Q.front!=Q.rear) Q.DeQueue(k); /隊(duì)頭元素出列并置為k for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w) if(!visitedw) /w為k的尚未訪問(wèn)的鄰接頂點(diǎn) visitedw=true; p