圖的搜索實現（鄰接矩陣）

摘 要  本課程設計主要解決圖的搜索實現，通過圖的鄰接矩陣實現深度優先搜索和廣度優先搜索。圖是一種較線形表和樹更復雜的數據結構，其應用極為廣泛，目前已滲入到語言學，邏輯學，物理，化學以及計算機科學等諸多領域中。在本課程設計中，系統開發平臺為Windows xp，程序設計設計語言主要采用C語言，程序運行平臺為Windows 2000/XP。程序開始后，通過輸入各結點與邊的相關數據，可以得出相應的深度優先和廣度優先搜索結果。

關鍵詞  程序設計；C語言；圖的鄰接矩陣；圖的深度優先搜索、廣度優先搜索
 
1 引  言
圖是一種較復雜的數據結構，圖的搜索在圖書索引，城市道路建設，人工智能等領域中發揮著重要作用。圖的搜索有深度優先搜索和廣度優先搜索，我們可以通過圖的鄰接矩陣或鄰接表實現圖的這兩種搜索。
本次程序設計我們通過C語言編寫程序實現圖的搜索。在編寫過程中我們將圖定義為鄰接矩陣類型，通過深度優先搜索遍歷和廣度優先搜索遍歷分別實現圖的搜索。
    我們學習兩年的有關C語言和數據結構的相關知識，而課程設計是將我們把所學的理論和生產實踐相結合的重要環節， 通過這次課程設計，可以使我們所學的專業技能得到鞏固、擴大、深入和系統化；培養綜合運用所學知識解決圖的搜索的能力，初步掌握數據結構程序設計的方法和步驟；使我們進一步提高編寫程序的效率；提高我們獨立鉆研問題的能力，培養嚴肅認真，實事求是，刻苦鉆研的工作作風。

2 開發工具介紹
C 語言是1972年由美國的Dennis Ritchie設計發明的, 并首次在UNIX操作系統DEC PDP-11 計算機上使用。 它由早期的編程語言 BCPL( Basic Combind Programming Language) 發展演變而來。在1970年, AT&T 貝爾實驗室的 Ken Thompson根據BCPL語言設計出較先進的并取名為 B的語言, 最后導了C 語言的問世。 隨著微型計算機的日益普及, 出現了許多C語言版本。由于沒有統一的標準, 使得這些C 語言之間出現了一些不一致的地方。為了改變這種情況, 美國國家標準研究所(ANSI)為C 語言制定了一套ANSI標準,成為現行的C語言標準。
C語言具有強大的功能，它具有以下特點：
1. C是中級語言
它把高級語言的基本結構和語句與低級語言的實用性結合起來。C 語言可以象匯編語言一樣對位、字節和地址進行操作, 而這三者是計算機最基本的工作單元。
2. C是結構式語言
結構式語言的顯著特點是代碼及數據的分隔化, 即程序的各個部分除了必要的信息交流外彼此獨立。這種結構化方式可使程序層次清晰, 便于使用、維護以及調試。C
語言是以函數形式提供給用戶的, 這些函數可方便的調用, 并具有多種循環、條件語句控制程序流向, 從而使程序完全結構化。
3. C語言功能齊全
C 語言具有各種各樣的數據類型, 并引入了指針概念, 可使程序效率更高。另外C 語言也具有強大的圖形功能,
支持多種顯示器和驅動器。而且計算功能、邏輯判斷功能也比較強大, 可以實現決策目的。
4. C語言適用范圍大
C 語言還有一個突出的優點就是適合于多種操作系統, 如DOS、UNIX,也適用于多種機型。
 3 相關知識
  
 圖的概念：圖是一種較線形表和樹更復雜的數據結構，是一種數據元素間為多對多關系的數據結構，加上一組基本操作構成的抽象數據類型，圖作為一種非線性數據結構，被廣泛應用于多個技術領域，諸如系統工程、化學分析、統計力學、遺傳學、控制論、計算機的人工智能、編譯系統等領域。
 圖的基本操作：創建、插入、刪除、查找等。
 圖的幾種存儲結構類型：圖的鄰接矩陣表示法，圖的鄰接表表示法
 深度優先搜索（DFS）:a、深度優先搜索類似于樹的前序遍歷，也是一遇到頂點就進行訪問。其特點是盡可能先對縱深方向進行搜索，因此很容易用遞歸算法實現。如果將遍歷過程中走過的邊連接起來，即可得到深度優先遍歷生成樹。b、深度優先搜索遍歷圖的算法：首先訪問指定的起始頂點v0，從v0出發，訪問v0的一個未被訪問過的鄰接頂點w1，再從w1出發，訪問w1的一個未被訪問過的頂點w2，然后從w2出發，訪問w2的一個未被訪問過的鄰接頂點w3。依次類推，直到一個所有鄰接頂點都被訪問過為止。
 廣度優先搜索（BFS）:廣度優先搜索類似于樹的按層次遍歷。首先訪問指定的起始點v0，從v0出發，訪問v0的所有未被訪問過的鄰接頂點w1，w2，… wk，然后再依次從w1，w2，… wk出發，訪問它們的所有未被訪問過的鄰接頂點，依次類推，直到圖中所有未被訪問過的鄰接頂點都被訪問過為止。廣度優先遍歷的特點是盡可能進行橫向搜索，即最先訪問的頂點其鄰接點也被先訪問。因此，借助一個隊列來保存已被訪問過的頂點序列。訪問一個頂點vi時（出隊），同時將vi相鄰的其余結點入隊。每個頂點只能入隊一次。

4 程序的設計與實現
4．1 程序相關算法偽代碼[3]
 圖的深度優先搜索算法偽代碼：
 DFS（v）//訪問由v到達的所有頂點
 1.  Visited(v)=1;
 2.  for鄰接于v的每個頂點w  do
 3．   if Visited(w)=0 then
 4.      DFS(w);
 5.    endif
 6.  endfor  
 7．end DFS
 
圖的廣度優先搜索算法偽代碼：
 BFS(v) //寬度優先搜索G，從頂點v開始執行
     // 所有已搜索的頂點i都標記為Visited(i)=1.
     //Visited的初始分量值全為0
 1. Visited(v)=1; u＝v;
 2. Q=[];//將Q初始化為空隊列
 3. loop
 4.   for 鄰接于u的所有頂點w  do
 5.     if Visited(w)=0 then
 6.       AddQ(w,Q); //將w放于隊列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 程序運行流程圖
程序開始運行后，其流程圖如下所示：

如圖4.1，程序開始運行后，選擇0或1分別構造有向圖和無向圖，然后根據程序的提示分別輸入圖的結點數，邊數和它們之間的對應關系，最后輸出深度優先搜索和廣度優先搜索的結果。
圖4.1程序運行流程圖

4．3 代碼分析
4．3．1 主要函數的功能：
（1）createmgraph(mgraph *g) 建立圖g的鄰接矩陣表示
（2）mgraph *g：申請圖g的鄰接矩陣表示空間
（3）createmgraph(g)：建立圖g
（4）dfsm(mgraph *g,int i)：對以鄰接矩陣表示的圖，以序號為i的頂點為出發點進行深度優先搜索
（5）bfsm(mgraph *g,int k)對以鄰接矩陣表示的圖，以序號為k的頂點作為出發點進行廣度優先搜索
（6）printf("visit vertex:%d ",g->vexs[i])：訪問序號為i的頂點
（7）printf("visit vertex:%d ",g->vexs[k])：訪問序號為k的頂點
（8）printf("the dfs is:") dfstraverse(g); 輸出對圖g進行深度優先搜索的結果
（9）printf("the bfs is:"); bfstraverse(g)；輸出對圖g進行廣度優先搜索的結果

4．3．2 本程序的數據結構：　
dfstraverse(mgraph *g)
　{//對以鄰接矩陣表示的圖，進行深度優先搜索
　　int i;
　　for(i=0;i<g->n;i++)//將圖的所有頂點設置為未訪問過
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//對圖*g進行深度優先搜索
　　　if(!visited[i])
　　　　dfsm(g,i);
　　printf("\n");
　}//end of dfstraverse

bfstraverse(mgraph *g)
　{//對以鄰接矩陣表示的圖，進行廣度優先搜索
　　int i;
　　for(i=0;i<g->n;i++)//將所有頂點設置為未訪問過
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//對鄰接矩陣表示的圖進行廣度優先搜索
　　　if(!visited[i])
　　　　bfsm(g,i);
　　printf("\n");
　}//end of bfstraverse

4．3．3 本程序的關鍵代碼：
#define maxvertexnum 100//設置鄰接矩陣的最大階數
#define queuesize 100//設置循環隊列的最大空間
typedef struct{
　　int front,rear,count,data[queuesize];
　}cirqueue;//循環隊列結構定義
typedef int vertextype;//設置圖的頂點信息為整型
typedef int edgetype;//設置邊上權值為整型
typedef struct{
　　vertextype vexs[maxvertexnum];//圖的頂點信息表
　　edgetype edges[maxvertexnum][maxvertexnum];//圖的鄰接矩陣
　　int n,e;//圖的頂點數和邊數
　}mgraph;//圖的鄰接矩陣表示結構定義

 main()//主函數
　{//建立用鄰接矩陣表示的圖，并進行深度優先搜索和廣度優先搜索
　　mgraph *g;
　　g=(mgraph*)malloc(sizeof(mgraph));//申請圖g的鄰接矩陣表示空間
　　createmgraph(g);//建立圖g
　　printf("the dfs is:");//對圖g進行深度優先搜索
　　dfstraverse(g);
　　printf("the bfs is:");//對圖g進行廣度優先搜索
　　bfstraverse(g);
　}
createmgraph(mgraph *g)
　//建立圖g的鄰接矩陣表示
　　int i,j,k,w;
　　int flag;
dfsm(mgraph *g,int i)
　//對以鄰接矩陣表示的圖，以序號為i的頂點為出發點進行深度優先搜索
dfstraverse(mgraph *g)
　//對以鄰接矩陣表示的圖，進行深度優先搜索
bfsm(mgraph *g,int k)
　//對以鄰接矩陣表示的圖，以序號為k的頂點作為出發點進行廣度優先搜索
bfstraverse(mgraph *g)
　//對以鄰接矩陣表示的圖，進行廣度優先搜索

 對關鍵代碼的說明：開始是建立圖的鄰接矩陣，對圖的結構類型的定義，在子程序中，完成對深度優先搜索和廣度優先搜索的建立，在以鄰接矩陣表示的圖中，分別進行深度優先搜索和廣度優先搜索，并在主函數中調用它們。

5調試與運行結果 
5．1 調試方法及調試過程
   調試方法： TurboC集成環境有很強的動態調試能力，在程序設計過程中，有如下幾種主要調試手段：（1）運行（Run： Run，ctrl-F9) （2）設置斷點 （break／watch： toggle breakpoint， Ctrl-F8） (3)變量查看及修改 （Debug：eva luate， CtrL-F4）（4）查看函數調用情況（Debug： Call stack， Ctrl-F3）（5）查找函數（Debug: Find function）（6）更新屏幕內容（Debug： Refresh disp1ay）（7）設置觀察對象（break/watch：Add watch，ctrl-F7）等。
 調試過程：程序第一次運行時，出現了頭文件無法辨析和C1202的錯誤，在把注釋，此問題得以解決，不過由于本程序大部分采用結構化程序設計方法，程序是DOS界面，并且數據都保存在內存中，因此穩定性不是很高。除了應嚴格按照數據的定義外，數值類數據不能輸入過大，在測試過程中曾由于輸入數據過大，發生了溢出錯誤，修改數據后此問題得以解決。在主函數的結尾還要加上getch()，否則會因為操作系統版本原因導致無法在TC環境中查看運行結果。
5．2 程序運行結果：
 本次測試數據用圖及其鄰接矩陣如圖5.1所示：
 
 圖5.1測試數據用圖
 
 
 
 ∞　3   3    ∞  ∞  ∞
                       3  ∞   ∞   3   4   ∞
 3  ∞   ∞   ∞  ∞   3
 ∞  3   ∞   ∞  ∞  ∞
 ∞  4   ∞   ∞  ∞  ∞
 ∞  ∞  3    ∞  ∞  ∞
 圖5 .2 測試數據用圖鄰接矩陣
 
 測試過程中此本次程序設計好后經調試運行后的結果截圖：（見圖）  
 圖5.3 選擇有向圖
如圖5.3：程序開始運行時會要求輸入圖的類型，此處輸入0表示選擇有向圖
 

 圖5.4 輸入圖的邊數和結點數
如圖5.4：在程序分別輸入結點數6和邊數5，再從1至6分別輸入結點數，構造圖的大小
 

 圖5.5 輸入圖的各結點和權值
如圖5.5：在程序中，分別輸入相連兩結點和連接兩結點的邊的權
 

                      圖5.6深度優先搜索輸出結果
如圖5.6：深度優先搜索輸出過程為1—2—4—5—3—6

 圖5 .7選擇無向圖
 
如圖5.7：程序開始運行時會要求輸入圖的類型，此處輸入1表示選擇無向圖

 圖5.8輸入圖的邊數和結點數
如圖5.8：在程序分別輸入結點數6和邊數5，再從1至6分別輸入結點數，構造圖的大小

 圖5.9輸入圖的各結點和權值
如圖5.9：在程序中，分別輸入相連兩結點和連接兩結點的邊的權

 圖5.10廣度優先搜索輸出結果
如圖5.10：廣度優先搜索輸出過程為1—2—3—4—5—6

6應用探討
 通過本次設計的最終程序我們可以看到：通過建立已定義好的圖的鄰接矩陣類型，然后用子函數寫出深度優先搜索遍歷及廣度優先搜索遍歷，再用主函數調用實現。這樣我們可以對圖進行周游，從而實現圖的搜索。而且從運行結果中還可以對兩種遍歷結果進行比較。雖然本程序生成的結果只是一排按圖的頂點的排序，但是我們在實際的軟件開發中可以將其運用到其中以實現我們日常的各種搜索軟件中。
 
7結束語
 由于平時對編程相關的知識掌握不夠深刻，在本次程序設計中遇到了很多麻煩，經常會出現改正一個錯誤產生更多錯誤的情況，很多語言運用都出現了錯誤，最后改用C語言，并在同學幫助下終于、完成了對程序的調試。本次程序設計實踐，使我更進一步的掌握了C語言編程的運用，并且在編寫程序中進一步學習了運用數據結構與算法實現程序功能，對圖的深度搜索，廣度搜索，有了很多新的理解，同時認識到了算法在編程中的重要性，不過由于時間緊迫，很多問題到現在還不能理解，課程設計所作的一些要求還沒有達到。
 正所謂臺上一分鐘，臺下十年功，只有平時多加刻苦，在我們遇到有關方面的問題時才不會顯得那么束手無策。
 
參考文獻
[1] 許卓群，楊冬青，唐世渭，張銘.數據結構與算法.北京：高等教育出版社，2005
[2] 陳志泊，王春玲.面向對象的程序設計語言——C++.北京：人民郵電出版社，2005
[3] 潭浩強. C程序設計.北京：清華大學出版社，2004

附錄：圖的搜索源程序清單
//圖的搜索實現
#include <stdio.h>
#define maxvertexnum 100//設置鄰接矩陣的最大階數
#define queuesize 100//設置循環隊列的最大空間
typedef struct{
　　int front,rear,count,data[queuesize];
　}cirqueue;//循環隊列結構定義
typedef int vertextype;//設置圖的頂點信息為整型
typedef int edgetype;//設置邊上權值為整型
typedef struct{
　　vertextype vexs[maxvertexnum];//圖的頂點信息表
　　edgetype edges[maxvertexnum][maxvertexnum];//圖的鄰接矩陣
　　int n,e;//圖的頂點數和邊數
　}mgraph;//圖的鄰接矩陣表示結構定義
typedef enum{FALSE,TRUE}boolean;
boolean visited[maxvertexnum];//頂點訪問標記向量

main()//主函數
　{//建立用鄰接矩陣表示的圖，并進行深度優先搜索和廣度優先搜索
　　mgraph *g;
　　g=(mgraph*)malloc(sizeof(mgraph));//申請圖g的鄰接矩陣表示空間
　　createmgraph(g);//建立圖g
　　printf("the dfs is:");//對圖g進行深度優先搜索
　　dfstraverse(g);
　　printf("the bfs is:");//對圖g進行廣度優先搜索
　　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的頂點數和邊數
　　printf("input nodes:\n");
　　for(i=0;i<g->n;i++)//輸入n個頂點的信息
　　　　scanf("%d",&(g->vexs[i]));
　　for(i=0;i<g->n;i++)//將鄰接矩陣數組初始化
　　　for(j=0;j<g->n;j++)
　　　　g->edges[i][j]=0;
　　for(k=0;k<g->e;k++){//讀入n有向邊對應的三元組(i,j,w),若構造有向圖，
　　　　　　　　　　　　//i為有向邊的弧尾，j是有向邊的弧頭，
                        //w是有向邊的權值（建立一般的有向圖時，可輸入1）
　　　　printf("input i,j,w:\n");
　　　　scanf("%d%d%d",&i,&j,&w);
　　　　g->edges[i][j]=w;
　　　　if (flag)//構造無向圖
　　　　　　g->edges[j][i]=w;
　　　}
　}

dfsm(mgraph *g,int i)
　{//對以鄰接矩陣表示的圖，以序號為i的頂點為出發點進行深度優先搜索
　　int j;
　　printf("visit vertex:%d ",g->vexs[i]);//訪問序號為i的頂點
　　visited[i]=TRUE;//將序號為i的頂點設置訪問過標記
　　for(j=0;j<g->n;j++)//掃描鄰接矩陣的第i行，做以下操作
　　　if ((g->edges[i][j]!=0)&&(!visited[j]))
　　　　　//尋找序號為i的頂點的未訪問過的鄰接點(設序號為k),
　　　　dfsm(g,j);//以序號為k的頂點為出發點進行深度優先搜索
　}//end of dfsm

dfstraverse(mgraph *g)
　{//對以鄰接矩陣表示的圖，進行深度優先搜索
　　int i;
　　for(i=0;i<g->n;i++)//將圖的所有頂點設置為未訪問過
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//對圖*g進行深度優先搜索
　　　if(!visited[i])
　　　　dfsm(g,i);
　　printf("\n");
　}//end of dfstraverse

bfsm(mgraph *g,int k)
　{//對以鄰接矩陣表示的圖，以序號為k的頂點作為出發點進行廣度優先搜索
　　int i,j;
　　cirqueue *q;
　　q=(cirqueue *)malloc(sizeof(cirqueue));//申請循環隊列空間*q
　　q->rear=q->front=q->count;//將循環隊列*q設置為空隊列
　　printf("visit vertex:%d ",g->vexs[k]);//訪問序號為k的頂點
　　visited[k]=TRUE;//將序號為k是結點設置為已訪問過
　　q->data[q->rear]=k;q->rear=(q->rear+1)%queuesize;q->count++;//將序號為k的頂點入隊
　　while(q->count){//若隊列不為空，則做以下操作
　　　　i=q->data[q->front];q->front=(q->front+1)%queuesize;q->count--;
　　　　　//將隊首元素(序號為i的頂點)出隊
　　for(j=0;j<g->n;j++)//尋找序號為i頂點的鄰接點，并做如下處理
　　　if((g->edges[i][j]!=0)&&(!visited[j])){//若序號為i的頂點有未訪問過鄰接點
　　　　　printf("visit vertex:%d ",g->vexs[j]);//訪問序號為j的頂點
　　　　　visited[j]=TRUE;//設置序號為j的頂點訪問過標記
　　　　　q->data[q->rear]=j;q->rear=(q->rear+1)%queuesize;q->count++;
　　　　　　//將序號為j的頂點入隊
　　　　}//end of if
　　　}//end of for
　}//end of bfsm

bfstraverse(mgraph *g)
　{//對以鄰接矩陣表示的圖，進行廣度優先搜索
　　int i;
　　for(i=0;i<g->n;i++)//將所有頂點設置為未訪問過
　　　　visited[i]=FALSE;
　　for(i=0;i<g->n;i++)//對鄰接矩陣表示的圖進行廣度優先搜索
　　　if(!visited[i])
　　　　bfsm(g,i);
　　printf("\n");
　}//end of bfstraverse