- 相關(guān)推薦
通過(guò)圖的鄰接矩陣實(shí)現(xiàn)圖的搜索實(shí)現(xiàn)(一)
摘 要 本課程設(shè)計(jì)主要解決圖的搜索實(shí)現(xiàn)，通過(guò)圖的鄰接矩陣實(shí)現(xiàn)深度優(yōu)先搜索和廣度優(yōu)先搜索。圖是一種較線形表和樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其應(yīng)用極為廣泛，目前已滲入到語(yǔ)言學(xué)，邏輯學(xué)，物理，化學(xué)以及計(jì)算機(jī)科學(xué)等諸多領(lǐng)域中。在本課程設(shè)計(jì)中，系統(tǒng)開(kāi)發(fā)平臺(tái)為Windows xp，程序設(shè)計(jì)設(shè)計(jì)語(yǔ)言主要采用C語(yǔ)言，程序運(yùn)行平臺(tái)為Windows 2000/XP。程序開(kāi)始后，通過(guò)輸入各結(jié)點(diǎn)與邊的相關(guān)數(shù)據(jù)，可以得出相應(yīng)的深度優(yōu)先和廣度優(yōu)先搜索結(jié)果。
關(guān)鍵詞 程序設(shè)計(jì)；C語(yǔ)言；圖的鄰接矩陣；圖的深度優(yōu)先搜索、廣度優(yōu)先搜索
1 引 言
圖是一種較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，圖的搜索在圖書(shū)索引，城市道路建設(shè)，人工智能等領(lǐng)域中發(fā)揮著重要作用。圖的搜索有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們可以通過(guò)圖的鄰接矩陣或鄰接表實(shí)現(xiàn)圖的這兩種搜索。
本次程序設(shè)計(jì)我們通過(guò)C語(yǔ)言編寫(xiě)程序?qū)崿F(xiàn)圖的搜索。在編寫(xiě)過(guò)程中我們將圖定義為鄰接矩陣類型，通過(guò)深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷分別實(shí)現(xiàn)圖的搜索。
我們學(xué)習(xí)兩年的有關(guān)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，而課程設(shè)計(jì)是將我們把所學(xué)的理論和生產(chǎn)實(shí)踐相結(jié)合的重要環(huán)節(jié)， 通過(guò)這次課程設(shè)計(jì)，可以使我們所學(xué)的專業(yè)技能得到鞏固、擴(kuò)大、深入和系統(tǒng)化；培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)解決圖的搜索的能力，初步掌握數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)的方法和步驟；使我們進(jìn)一步提高編寫(xiě)程序的效率；提高我們獨(dú)立鉆研問(wèn)題的能力，培養(yǎng)嚴(yán)肅認(rèn)真，實(shí)事求是，刻苦鉆研的工作作風(fēng)。
2 開(kāi)發(fā)工具介紹
C 語(yǔ)言是1972年由美國(guó)的Dennis Ritchie設(shè)計(jì)發(fā)明的, 并首次在UNIX操作系統(tǒng)DEC PDP-11 計(jì)算機(jī)上使用。 它由早期的編程語(yǔ)言 BCPL( Basic Combind Programming Language) 發(fā)展演變而來(lái)。在1970年, AT&T 貝爾實(shí)驗(yàn)室的 Ken Thompson根據(jù)BCPL語(yǔ)言設(shè)計(jì)出較先進(jìn)的并取名為 B的語(yǔ)言, 最后導(dǎo)了C 語(yǔ)言的問(wèn)世。 隨著微型計(jì)算機(jī)的日益普及, 出現(xiàn)了許多C語(yǔ)言版本。由于沒(méi)有統(tǒng)一的標(biāo)準(zhǔn), 使得這些C 語(yǔ)言之間出現(xiàn)了一些不一致的地方。為了改變這種情況, 美國(guó)國(guó)家標(biāo)準(zhǔn)研究所(ANSI)為C 語(yǔ)言制定了一套ANSI標(biāo)準(zhǔn),成為現(xiàn)行的C語(yǔ)言標(biāo)準(zhǔn)。
C語(yǔ)言具有強(qiáng)大的功能，它具有以下特點(diǎn)：
1. C是中級(jí)語(yǔ)言
它把高級(jí)語(yǔ)言的基本結(jié)構(gòu)和語(yǔ)句與低級(jí)語(yǔ)言的實(shí)用性結(jié)合起來(lái)。C 語(yǔ)言可以象匯編語(yǔ)言一樣對(duì)位、字節(jié)和地址進(jìn)行操作, 而這三者是計(jì)算機(jī)最基本的工作單元。
2. C是結(jié)構(gòu)式語(yǔ)言
結(jié)構(gòu)式語(yǔ)言的顯著特點(diǎn)是代碼及數(shù)據(jù)的分隔化, 即程序的各個(gè)部分除了必要的信息交流外彼此獨(dú)立。這種結(jié)構(gòu)化方式可使程序?qū)哟吻逦? 便于使用、維護(hù)以及調(diào)試。C
語(yǔ)言是以函數(shù)形式提供給用戶的, 這些函數(shù)可方便的調(diào)用, 并具有多種循環(huán)、條件語(yǔ)句控制程序流向, 從而使程序完全結(jié)構(gòu)化。
3. C語(yǔ)言功能齊全
C 語(yǔ)言具有各種各樣的數(shù)據(jù)類型, 并引入了指針概念, 可使程序效率更高。另外C 語(yǔ)言也具有強(qiáng)大的圖形功能,
支持多種顯示器和驅(qū)動(dòng)器。而且計(jì)算功能、邏輯判斷功能也比較強(qiáng)大, 可以實(shí)現(xiàn)決策目的。
4. C語(yǔ)言適用范圍大
C 語(yǔ)言還有一個(gè)突出的優(yōu)點(diǎn)就是適合于多種操作系統(tǒng), 如DOS、UNIX,也適用于多種機(jī)型。
3 相關(guān)知識(shí)
圖的概念：圖是一種較線形表和樹(shù)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，是一種數(shù)據(jù)元素間為多對(duì)多關(guān)系的數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型，圖作為一種非線性數(shù)據(jù)結(jié)構(gòu)，被廣泛應(yīng)用于多個(gè)技術(shù)領(lǐng)域，諸如系統(tǒng)工程、化學(xué)分析、統(tǒng)計(jì)力學(xué)、遺傳學(xué)、控制論、計(jì)算機(jī)的人工智能、編譯系統(tǒng)等領(lǐng)域。
圖的基本操作：創(chuàng)建、插入、刪除、查找等。
圖的幾種存儲(chǔ)結(jié)構(gòu)類型：圖的鄰接矩陣表示法，圖的鄰接表表示法
深度優(yōu)先搜索（DFS）:a、深度優(yōu)先搜索類似于樹(shù)的前序遍歷，也是一遇到頂點(diǎn)就進(jìn)行訪問(wèn)。其特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索，因此很容易用遞歸算法實(shí)現(xiàn)。如果將遍歷過(guò)程中走過(guò)的邊連接起來(lái)，即可得到深度優(yōu)先遍歷生成樹(shù)。b、深度優(yōu)先搜索遍歷圖的算法：首先訪問(wèn)指定的起始頂點(diǎn)v0，從v0出發(fā)，訪問(wèn)v0的一個(gè)未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w1，再?gòu)膚1出發(fā)，訪問(wèn)w1的一個(gè)未被訪問(wèn)過(guò)的頂點(diǎn)w2，然后從w2出發(fā)，訪問(wèn)w2的一個(gè)未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w3。依次類推，直到一個(gè)所有鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止。
廣度優(yōu)先搜索（BFS）:廣度優(yōu)先搜索類似于樹(shù)的按層次遍歷。首先訪問(wèn)指定的起始點(diǎn)v0，從v0出發(fā)，訪問(wèn)v0的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)w1，w2，… wk，然后再依次從w1，w2，… wk出發(fā)，訪問(wèn)它們的所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)，依次類推，直到圖中所有未被訪問(wèn)過(guò)的鄰接頂點(diǎn)都被訪問(wèn)過(guò)為止。廣度優(yōu)先遍歷的特點(diǎn)是盡可能進(jìn)行橫向搜索，即最先訪問(wèn)的頂點(diǎn)其鄰接點(diǎn)也被先訪問(wèn)。因此，借助一個(gè)隊(duì)列來(lái)保存已被訪問(wèn)過(guò)的頂點(diǎn)序列。訪問(wèn)一個(gè)頂點(diǎn)vi時(shí)（出隊(duì)），同時(shí)將vi相鄰的其余結(jié)點(diǎn)入隊(duì)。每個(gè)頂點(diǎn)只能入隊(duì)一次。
4 程序的設(shè)計(jì)與實(shí)現(xiàn)
4．1 程序相關(guān)算法偽代碼[3]
圖的深度優(yōu)先搜索算法偽代碼：
DFS（v）//訪問(wèn)由v到達(dá)的所有頂點(diǎn)
1. Visited(v)=1;
2. for鄰接于v的每個(gè)頂點(diǎn)w do
3． if Visited(w)=0 then
4. DFS(w);
5. endif
6. endfor
7．end DFS
圖的廣度優(yōu)先搜索算法偽代碼：
BFS(v) //寬度優(yōu)先搜索G，從頂點(diǎn)v開(kāi)始執(zhí)行
// 所有已搜索的頂點(diǎn)i都標(biāo)記為Visited(i)=1.
//Visited的初始分量值全為0
1. Visited(v)=1; u＝v;
2. Q=[];//將Q初始化為空隊(duì)列
3. loop
4. for 鄰接于u的所有頂點(diǎn)w do
5. if Visited(w)=0 then
6. AddQ(w,Q); //將w放于隊(duì)列Q之尾
7. Visited(w)=1;
8. endif
9. endfor
10． if Q為空 then return； endif
11． DelHead(u,Q);
12. endloop
13.end BFS
4．2 程序運(yùn)行流程圖
程序開(kāi)始運(yùn)行后，其流程圖如下所示：
如圖4.1，程序開(kāi)始運(yùn)行后，選擇0或1分別構(gòu)造有向圖和無(wú)向圖，然后根據(jù)程序的提示分別輸入圖的結(jié)點(diǎn)數(shù)，邊數(shù)和它們之間的對(duì)應(yīng)關(guān)系，最后輸出深度優(yōu)先搜索和廣度優(yōu)先搜索的結(jié)果。
圖4.1程序運(yùn)行流程圖
4．3 代碼分析
4．3．1 主要函數(shù)的功能：
（1）createmgraph(mgraph *g) 建立圖g的鄰接矩陣表示
（2）mgraph *g：申請(qǐng)圖g的鄰接矩陣表示空間
（3）createmgraph(g)：建立圖g
（4）dfsm(mgraph *g,int i)：對(duì)以鄰接矩陣表示的圖，以序號(hào)為i的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行深度優(yōu)先搜索
（5）bfsm(mgraph *g,int k)對(duì)以鄰接矩陣表示的圖，以序號(hào)為k的頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行廣度優(yōu)先搜索
（6）printf("visit vertex:%d ",g->vexs[i])：訪問(wèn)序號(hào)為i的頂點(diǎn)
（7）printf("visit vertex:%d ",g->vexs[k])：訪問(wèn)序號(hào)為k的頂點(diǎn)
（8）printf("the dfs is:") dfstraverse(g); 輸出對(duì)圖g進(jìn)行深度優(yōu)先搜索的結(jié)果
（9）printf("the bfs is:"); bfstraverse(g)；輸出對(duì)圖g進(jìn)行廣度優(yōu)先搜索的結(jié)果
4．3．2 本程序的數(shù)據(jù)結(jié)構(gòu)：
dfstraverse(mgraph *g)
{//對(duì)以鄰接矩陣表示的圖，進(jìn)行深度優(yōu)先搜索
int i;
for(i=0;i<g->n;i++)//將圖的所有頂點(diǎn)設(shè)置為未訪問(wèn)過(guò)
visited[i]=FALSE;
for(i=0;i<g->n;i++)//對(duì)圖*g進(jìn)行深度優(yōu)先搜索
if(!visited[i])
dfsm(g,i);
printf("\n");
}//end of dfstraverse
bfstraverse(mgraph *g)
{//對(duì)以鄰接矩陣表示的圖，進(jìn)行廣度優(yōu)先搜索
int i;
for(i=0;i<g->n;i++)//將所有頂點(diǎn)設(shè)置為未訪問(wèn)過(guò)
visited[i]=FALSE;
for(i=0;i<g->n;i++)//對(duì)鄰接矩陣表示的圖進(jìn)行廣度優(yōu)先搜索
if(!visited[i])
bfsm(g,i);
printf("\n");
}//end of bfstraverse
4．3．3 本程序的關(guān)鍵代碼：
#define maxvertexnum 100//設(shè)置鄰接矩陣的最大階數(shù)
#define queuesize 100//設(shè)置循環(huán)隊(duì)列的最大空間
typedef struct{
int front,rear,count,data[queuesize];
}cirqueue;//循環(huán)隊(duì)列結(jié)構(gòu)定義
typedef int vertextype;//設(shè)置圖的頂點(diǎn)信息為整型
typedef int edgetype;//設(shè)置邊上權(quán)值為整型
typedef struct{
vertextype vexs[maxvertexnum];//圖的頂點(diǎn)信息表
edgetype edges[maxvertexnum][maxvertexnum];//圖的鄰接矩陣
int n,e;//圖的頂點(diǎn)數(shù)和邊數(shù)
}mgraph;//圖的鄰接矩陣表示結(jié)構(gòu)定義
main()//主函數(shù)
{//建立用鄰接矩陣表示的圖，并進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索
mgraph *g;
g=(mgraph*)malloc(sizeof(mgraph));//申請(qǐng)圖g的鄰接矩陣表示空間
createmgraph(g);//建立圖g
printf("the dfs is:");//對(duì)圖g進(jìn)行深度優(yōu)先搜索
dfstraverse(g);
printf("the bfs is:");//對(duì)圖g進(jìn)行廣度優(yōu)先搜索
bfstraverse(g);
}
createmgraph(mgraph *g)
//建立圖g的鄰接矩陣表示
int i,j,k,w;
int flag;
dfsm(mgraph *g,int i)
//對(duì)以鄰接矩陣表示的圖，以序號(hào)為i的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行深度優(yōu)先搜索
dfstraverse(mgraph *g)
//對(duì)以鄰接矩陣表示的圖，進(jìn)行深度優(yōu)先搜索
bfsm(mgraph *g,int k)
//對(duì)以鄰接矩陣表示的圖，以序號(hào)為k的頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行廣度優(yōu)先搜索
bfstraverse(mgraph *g)
//對(duì)以鄰接矩陣表示的圖，進(jìn)行廣度優(yōu)先搜索
對(duì)關(guān)鍵代碼的說(shuō)明：開(kāi)始是建立圖的鄰接矩陣，對(duì)圖的結(jié)構(gòu)類型的定義，在子程序中，完成對(duì)深度優(yōu)先搜索和廣度優(yōu)先搜索的建立，在以鄰接矩陣表示的圖中，分別進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，并在主函數(shù)中調(diào)用它們。
5調(diào)試與運(yùn)行結(jié)果
5．1 調(diào)試方法及調(diào)試過(guò)程
調(diào)試方法： TurboC集成環(huán)境有很強(qiáng)的動(dòng)態(tài)調(diào)試能力，在程序設(shè)計(jì)過(guò)程中，有如下幾種主要調(diào)試手段：（1）運(yùn)行（Run： Run，ctrl-F9) （2）設(shè)置斷點(diǎn) （break／watch： toggle breakpoint， Ctrl-F8） (3)變量查看及修改 （Debug：Evaluate， CtrL-F4）（4）查看函數(shù)調(diào)用情況（Debug： Call stack， Ctrl-F3）（5）查找函數(shù)（Debug: Find function）（6）更新屏幕內(nèi)容（Debug： Refresh disp1ay）（7）設(shè)置觀察對(duì)象（break/watch：Add watch，ctrl-F7）等。
調(diào)試過(guò)程：程序第一次運(yùn)行時(shí)，出現(xiàn)了頭文件無(wú)法辨析和C1202的錯(cuò)誤，在把注釋，此問(wèn)題得以解決，不過(guò)由于本程序大部分采用結(jié)構(gòu)化程序設(shè)計(jì)方法，程序是DOS界面，并且數(shù)據(jù)都保存在內(nèi)存中，因此穩(wěn)定性不是很高。除了應(yīng)嚴(yán)格按照數(shù)據(jù)的定義外，數(shù)值類數(shù)據(jù)不能輸入過(guò)大，在測(cè)試過(guò)程中曾由于輸入數(shù)據(jù)過(guò)大，發(fā)生了溢出錯(cuò)誤，修改數(shù)據(jù)后此問(wèn)題得以解決。在主函數(shù)的結(jié)尾還要加上getch()，否則會(huì)因?yàn)椴僮飨到y(tǒng)版本原因?qū)е聼o(wú)法在TC環(huán)境中查看運(yùn)行結(jié)果。
5．2 程序運(yùn)行結(jié)果：
本次測(cè)試數(shù)據(jù)用圖及其鄰接矩陣如圖5.1所示：
圖5.1測(cè)試數(shù)據(jù)用圖
∞ 3 3 ∞ ∞ ∞
3 ∞ ∞ 3 4 ∞
3 ∞ ∞ ∞ ∞ 3
∞ 3 ∞ ∞ ∞ ∞
∞ 4 ∞ ∞ ∞ ∞
∞ ∞ 3 ∞ ∞ ∞
圖5 .2 測(cè)試數(shù)據(jù)用圖鄰接矩陣
測(cè)試過(guò)程中此本次程序設(shè)計(jì)好后經(jīng)調(diào)試運(yùn)行后的結(jié)果截圖：（見(jiàn)圖）
圖5.3 選擇有向圖
如圖5.3：程序開(kāi)始運(yùn)行時(shí)會(huì)要求輸入圖的類型，此處輸入0表示選擇有向圖
圖5.4 輸入圖的邊數(shù)和結(jié)點(diǎn)數(shù)
如圖5.4：在程序分別輸入結(jié)點(diǎn)數(shù)6和邊數(shù)5，再?gòu)?至6分別輸入結(jié)點(diǎn)數(shù)，構(gòu)造圖的大小
圖5.5 輸入圖的各結(jié)點(diǎn)和權(quán)值
如圖5.5：在程序中，分別輸入相連兩結(jié)點(diǎn)和連接兩結(jié)點(diǎn)的邊的權(quán)
圖5.6深度優(yōu)先搜索輸出結(jié)果
如圖5.6：深度優(yōu)先搜索輸出過(guò)程為1—2—4—5—3—6
圖5 .7選擇無(wú)向圖
如圖5.7：程序開(kāi)始運(yùn)行時(shí)會(huì)要求輸入圖的類型，此處輸入1表示選擇無(wú)向圖
圖5.8輸入圖的邊數(shù)和結(jié)點(diǎn)數(shù)
如圖5.8：在程序分別輸入結(jié)點(diǎn)數(shù)6和邊數(shù)5，再?gòu)?至6分別輸入結(jié)點(diǎn)數(shù)，構(gòu)造圖的大小
圖5.9輸入圖的各結(jié)點(diǎn)和權(quán)值
如圖5.9：在程序中，分別輸入相連兩結(jié)點(diǎn)和連接兩結(jié)點(diǎn)的邊的權(quán)
圖5.10廣度優(yōu)先搜索輸出結(jié)果
如圖5.10：廣度優(yōu)先搜索輸出過(guò)程為1—2—3—4—5—6
6應(yīng)用探討
通過(guò)本次設(shè)計(jì)的最終程序我們可以看到：通過(guò)建立已定義好的圖的鄰接矩陣類型，然后用子函數(shù)寫(xiě)出深度優(yōu)先搜索遍歷及廣度優(yōu)先搜索遍歷，再用主函數(shù)調(diào)用實(shí)現(xiàn)。這樣我們可以對(duì)圖進(jìn)行周游，從而實(shí)現(xiàn)圖的搜索。而且從運(yùn)行結(jié)果中還可以對(duì)兩種遍歷結(jié)果進(jìn)行比較。雖然本程序生成的結(jié)果只是一排按圖的頂點(diǎn)的排序，但是我們?cè)趯?shí)際的軟件開(kāi)發(fā)中可以將其運(yùn)用到其中以實(shí)現(xiàn)我們?nèi)粘５母鞣N搜索軟件中。
7結(jié)束語(yǔ)
由于平時(shí)對(duì)編程相關(guān)的知識(shí)掌握不夠深刻，在本次程序設(shè)計(jì)中遇到了很多麻煩，經(jīng)常會(huì)出現(xiàn)改正一個(gè)錯(cuò)誤產(chǎn)生更多錯(cuò)誤的情況，很多語(yǔ)言運(yùn)用都出現(xiàn)了錯(cuò)誤，最后改用C語(yǔ)言，并在同學(xué)幫助下終于、完成了對(duì)程序的調(diào)試。本次程序設(shè)計(jì)實(shí)踐，使我更進(jìn)一步的掌握了C語(yǔ)言編程的運(yùn)用，并且在編寫(xiě)程序中進(jìn)一步學(xué)習(xí)了運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)程序功能，對(duì)圖的深度搜索，廣度搜索，有了很多新的理解，同時(shí)認(rèn)識(shí)到了算法在編程中的重要性，不過(guò)由于時(shí)間緊迫，很多問(wèn)題到現(xiàn)在還不能理解，課程設(shè)計(jì)所作的一些要求還沒(méi)有達(dá)到。
正所謂臺(tái)上一分鐘，臺(tái)下十年功，只有平時(shí)多加刻苦，在我們遇到有關(guān)方面的問(wèn)題時(shí)才不會(huì)顯得那么束手無(wú)策。
參考文獻(xiàn)
[1] 許卓群，楊冬青，唐世渭，張銘.數(shù)據(jù)結(jié)構(gòu)與算法.北京：高等教育出版社，2005
[2] 陳志泊，王春玲.面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言——C++.北京：人民郵電出版社，2005
[3] 潭浩強(qiáng). C程序設(shè)計(jì).北京：清華大學(xué)出版社，2004
附錄：圖的搜索源程序清單
//圖的搜索實(shí)現(xiàn)
#include <stdio.h>
#define maxvertexnum 100//設(shè)置鄰接矩陣的最大階數(shù)
#define queuesize 100//設(shè)置循環(huán)隊(duì)列的最大空間
typedef struct{
int front,rear,count,data[queuesize];
}cirqueue;//循環(huán)隊(duì)列結(jié)構(gòu)定義
typedef int vertextype;//設(shè)置圖的頂點(diǎn)信息為整型
typedef int edgetype;//設(shè)置邊上權(quán)值為整型
typedef struct{
vertextype vexs[maxvertexnum];//圖的頂點(diǎn)信息表
edgetype edges[maxvertexnum][maxvertexnum];//圖的鄰接矩陣
int n,e;//圖的頂點(diǎn)數(shù)和邊數(shù)
}mgraph;//圖的鄰接矩陣表示結(jié)構(gòu)定義
typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];//頂點(diǎn)訪問(wèn)標(biāo)記向量
main()//主函數(shù)
{//建立用鄰接矩陣表示的圖，并進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索
mgraph *g;
g=(mgraph*)malloc(sizeof(mgraph));//申請(qǐng)圖g的鄰接矩陣表示空間
createmgraph(g);//建立圖g
printf("the dfs is:");//對(duì)圖g進(jìn)行深度優(yōu)先搜索
dfstraverse(g);
printf("the bfs is:");//對(duì)圖g進(jìn)行廣度優(yōu)先搜索
bfstraverse(g);
}
createmgraph(mgraph *g)
{//建立圖g的鄰接矩陣表示
int i,j,k,w;
int flag;
printf("\ncreat:\n");
printf("digragh--0\n");
printf("undigragh--1\n");
scanf("%d",&flag);
printf("input n,e\n");
scanf("%d%d",&g->n,&g->e);//輸入圖*g的頂點(diǎn)數(shù)和邊數(shù)
printf("input nodes:\n");
for(i=0;i<g->n;i++)//輸入n個(gè)頂點(diǎn)的信息
scanf("%d",&(g->vexs[i]));
for(i=0;i<g->n;i++)//將鄰接矩陣數(shù)組初始化
for(j=0;j<g->n;j++)
g->edges[i][j]=0;
for(k=0;k<g->e;k++){//讀入n有向邊對(duì)應(yīng)的三元組(i,j,w),若構(gòu)造有向圖，
//i為有向邊的弧尾，j是有向邊的弧頭，
//w是有向邊的權(quán)值（建立一般的有向圖時(shí)，可輸入1）
printf("input i,j,w:\n");
scanf("%d%d%d",&i,&j,&w);
g->edges[i][j]=w;
if (flag)//構(gòu)造無(wú)向圖
g->edges[j][i]=w;
}
}
dfsm(mgraph *g,int i)
{//對(duì)以鄰接矩陣表示的圖，以序號(hào)為i的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行深度優(yōu)先搜索
int j;
printf("visit vertex:%d ",g->vexs[i]);//訪問(wèn)序號(hào)為i的頂點(diǎn)
visited[i]=TRUE;//將序號(hào)為i的頂點(diǎn)設(shè)置訪問(wèn)過(guò)標(biāo)記
for(j=0;j<g->n;j++)//掃描鄰接矩陣的第i行，做以下操作
if ((g->edges[i][j]!=0)&&(!visited[j]))
//尋找序號(hào)為i的頂點(diǎn)的未訪問(wèn)過(guò)的鄰接點(diǎn)(設(shè)序號(hào)為k),
dfsm(g,j);//以序號(hào)為k的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行深度優(yōu)先搜索
}//end of dfsm
dfstraverse(mgraph *g)
{//對(duì)以鄰接矩陣表示的圖，進(jìn)行深度優(yōu)先搜索
int i;
for(i=0;i<g->n;i++)//將圖的所有頂點(diǎn)設(shè)置為未訪問(wèn)過(guò)
visited[i]=FALSE;
for(i=0;i<g->n;i++)//對(duì)圖*g進(jìn)行深度優(yōu)先搜索
if(!visited[i])
dfsm(g,i);
printf("\n");
}//end of dfstraverse
bfsm(mgraph *g,int k)
{//對(duì)以鄰接矩陣表示的圖，以序號(hào)為k的頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行廣度優(yōu)先搜索
int i,j;
cirqueue *q;
q=(cirqueue *)malloc(sizeof(cirqueue));//申請(qǐng)循環(huán)隊(duì)列空間*q
q->rear=q->front=q->count;//將循環(huán)隊(duì)列*q設(shè)置為空隊(duì)列
printf("visit vertex:%d ",g->vexs[k]);//訪問(wèn)序號(hào)為k的頂點(diǎn)
visited[k]=TRUE;//將序號(hào)為k是結(jié)點(diǎn)設(shè)置為已訪問(wèn)過(guò)
q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//將序號(hào)為k的頂點(diǎn)入隊(duì)
while(q->count){//若隊(duì)列不為空，則做以下操作
i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;
//將隊(duì)首元素(序號(hào)為i的頂點(diǎn))出隊(duì)
for(j=0;j<g->n;j++)//尋找序號(hào)為i頂點(diǎn)的鄰接點(diǎn)，并做如下處理
if((g->edges[i][j]!=0)&&(!visited[j])){//若序號(hào)為i的頂點(diǎn)有未訪問(wèn)過(guò)鄰接點(diǎn)
printf("visit vertex:%d ",g->vexs[j]);//訪問(wèn)序號(hào)為j的頂點(diǎn)
visited[j]=TRUE;//設(shè)置序號(hào)為j的頂點(diǎn)訪問(wèn)過(guò)標(biāo)記
q->data[q->rear]=j;q->rear=(q->rear+1)%queuesize;q->count++;
//將序號(hào)為j的頂點(diǎn)入隊(duì)
}//end of if
}//end of for
}//end of bfsm
bfstraverse(mgraph *g)
{//對(duì)以鄰接矩陣表示的圖，進(jìn)行廣度優(yōu)先搜索
int i;
for(i=0;i<g->n;i++)//將所有頂點(diǎn)設(shè)置為未訪問(wèn)過(guò)
visited[i]=FALSE;
for(i=0;i<g->n;i++)//對(duì)鄰接矩陣表示的圖進(jìn)行廣度優(yōu)先搜索
if(!visited[i])
bfsm(g,i);
printf("\n");
}//end of bfstraverse
【通過(guò)圖的鄰接矩陣實(shí)現(xiàn)圖的搜索實(shí)現(xiàn)(一)】相關(guān)文章：
基于MapObjects控件的鷹眼圖實(shí)現(xiàn)方法03-07
Web搜索引擎的智能搜索設(shè)計(jì)與實(shí)現(xiàn)03-08
CPM搜索引擎的設(shè)計(jì)與實(shí)現(xiàn)03-08
數(shù)字電視衛(wèi)星信號(hào)的搜索方案的研究與實(shí)現(xiàn)03-07
刑罰實(shí)現(xiàn)探析03-18
實(shí)時(shí)混音的實(shí)現(xiàn)03-18