設為首頁收藏本站

                      LUPA開源社區

                       找回密碼
                       注冊
                      文章 帖子 博客
                      LUPA開源社區 首頁 業界資訊 技術文摘 查看內容

                      自己動手實現圖的BFS和DFS(附完整源碼)

                      2014-2-25 15:24| 發布者: 紅黑魂| 查看: 117760| 評論: 2|原作者: 蘭亭風雨|來自: CSDN博客

                      摘要: 圖的存儲結構 本文的重點在于圖的深度優先搜索(DFS)和廣度優先搜索(BFS),因此不再對圖的基本概念做過多的介紹,但是要先大致了解下圖的幾種常見的存儲結構。 鄰接矩陣 鄰接矩陣既可以用來存儲無向圖,也可以 ...

                      圖的存儲結構

                          本文的重點在于圖的深度優先搜索(DFS)和廣度優先搜索(BFS),因此不再對圖的基本概念做過多的介紹,但是要先大致了解下圖的幾種常見的存儲結構。

                          鄰接矩陣

                          鄰接矩陣既可以用來存儲無向圖,也可以用來存儲有向圖。該結構實際上就是用一個二維數組(鄰接矩陣)來存儲頂點的信息和頂點之間的關系(有向圖的弧或無向圖的邊)。其描述形式如下:

                      1. //圖的鄰接矩陣存儲表示  
                      2. #define MAX_NUM 20 // 最大頂點個數  
                      3. enum GraphKind{GY,GN}; // {有向圖,無向圖}  
                      4. typedef struct  
                      5. {  
                      6.    VRType adj; // 頂點關系類型。對無權圖,用1(是)或0(否)表示是否相鄰;對帶權圖,則為權值  
                      7.    InfoType *info; // 與該弧或邊相關信息的指針(可無)  
                      8. }ArcCell,AdjMatrix[MAX_NUM][MAX_NUM]; // 二維數組  
                      9. typedef struct  
                      10. {  
                      11.    VertexType vexs[MAX_NUM]; // 頂點向量  
                      12.    AdjMatrix arcs; // 鄰接矩陣  
                      13.    int vexnum,arcnum; // 圖的當前頂點數和弧(邊)數  
                      14.    GraphKind kind; // 圖的種類標志  
                      15. }Graph;  
                          我們分別看下面兩個圖,左邊為有向圖,右邊為無向圖


                          上面兩個圖均為無權圖,我們假設存儲的時候,V0的序號為0,V1的序號為1,V2的序號為2。。。,且adj為1表示兩頂點間沒有沒有連接,為0時表示有連接。則有向圖的鄰接矩陣如下圖左邊的矩陣所示,無向圖的鄰接矩陣如下圖右邊的矩陣所示;


                          根據鄰接矩陣很容易判斷圖中任意兩個頂點之間連通與否,并可以求出各個頂點的度。
                          1、對于無向圖,觀察右邊的矩陣,發現頂點Vi的度即是鄰接矩陣中第i行(或第i列)的元素之和。
                          2、對于有向圖,由于需要分別計算出度和入讀,觀察左邊的矩陣,發現頂點Vi的出度即為鄰接矩陣第i行元素之和,入度即為鄰接矩陣第i列元素之和,因此頂點Vi的度即為鄰接矩陣中第i行元素和第i列元素之和。
                          很明顯,鄰接矩陣所占用的存儲空間與圖的邊數或弧數無關,因此適用于邊數或弧數較多的稠密圖。

                          鄰接表

                          鄰接表是圖的一種鏈式存儲結構,既適合于存儲無向圖,也適合于存儲有向圖。在鄰接表中,用一個一維數組存儲圖中的每個頂點的信息,同時為每個頂點建立一個單鏈表,鏈表中的節點保存依附在該頂點上的邊或弧的信息。其描述形式如下
                      1. //圖的鄰接表存儲表示  
                      2. #define MAX_NUM 20  
                      3. enum GraphKind{GY,GN}; // {有向圖,無向圖}  
                      4. typedef struct   
                      5. {  
                      6.    int adjvex; // 該弧所指向的頂點或邊的另一個頂點的位置  
                      7.    ArcNode *nextarc; // 指向下一條弧或邊的指針  
                      8.    InfoType *info; // 與弧或邊相關信息的指針(可無)  
                      9. }ArcNode;// 表結點  
                      10. typedef struct  
                      11. {  
                      12.    VertexType data; // 頂點信息  
                      13.    ArcNode *firstarc; // 第一個表結點的地址,指向第一條依附該頂點的弧或邊的指針  
                      14. }VNode,AdjList[MAX_NUM]; // 頭結點  
                      15. struct   
                      16. {  
                      17.    AdjList vertices;  
                      18.    int vexnum,arcnum; // 圖的當前頂點數和弧(邊)數  
                      19.    GraphKind kind; // 圖的種類標志  
                      20. }Graph;  
                          依然以上面的有向圖和無向圖為例,采用鄰接表來存儲,可以得到對應的存儲形式如下:


                          在鄰接表上容易找到任意一個頂點的第一個鄰接點和下一個鄰接點,但是要判定任意兩個頂點之間是否有邊或弧需搜索兩個頂點對應的鏈表,不及鄰接矩陣方便。
                          很明顯,鄰接表所占用的存儲空間與圖的邊數或弧數有關,因此適用于邊數或弧數較少的稀疏圖。

                          十字鏈表

                          十字鏈表也是一種鏈式存儲結構,用來表示有向圖,它在有向圖鄰接表的基礎上加入了指向弧尾的指針。表示形式如下:
                      1. //有向圖的十字鏈表存儲表示  
                      2. #define MAX_NUM 20  
                      3. typedef struct // 弧結點  
                      4. {  
                      5.   int tailvex,headvex; // 該弧的尾和頭頂點的位置  
                      6.   ArcBox *hlink,*tlink; // 分別為弧頭相同和弧尾相同的弧的鏈域  
                      7.   InfoType *info; // 該弧相關信息的指針,可指向權值或其他信息(可無)  
                      8. }ArcBox;  
                      9. typedef struct // 頂點結點  
                      10. {  
                      11.   VertexType data;  
                      12.   ArcBox *firstin,*firstout; // 分別指向該頂點第一條入弧和出弧  
                      13. }VexNode;  
                      14. struct  
                      15. {  
                      16.   VexNode xlist[MAX_NUM]; // 表頭向量(數組)  
                      17.   int vexnum,arcnum; // 有向圖的當前頂點數和弧數  
                      18. }Graph;      
                          其思想也很容易理解,這里不再細說。
                          在十字鏈表中,既容易找到以某個頂點為尾的弧,也容易找到以某個頂點為頭的弧,因而容易求得頂點的出度和入度。

                          鄰接多重表

                          鄰接多重表也是一種鏈式存儲結構,用來表示無向圖,與有向圖的十字鏈表相似,這里也不再細說,直接給出其表示形式:
                      1. //無向圖的鄰接多重表存儲表示  
                      2.  #define MAX_NUM 20  
                      3.  typedef struct   
                      4.  {  
                      5.    VisitIf mark; // 訪問標記  
                      6.    int ivex,jvex; // 該邊依附的兩個頂點的位置  
                      7.    EBox *ilink,*jlink; // 分別指向依附這兩個頂點的下一條邊  
                      8.    InfoType *info; // 該邊信息指針,可指向權值或其他信息  
                      9.  }EBox;  
                      10.  typedef struct  
                      11.  {  
                      12.    VertexType data;  
                      13.    EBox *firstedge; // 指向第一條依附該頂點的邊  
                      14.  }VexBox;  
                      15.  typedef struct   
                      16.  {  
                      17.    VexBox adjmulist[MAX_NUM];  
                      18.    int vexnum,edgenum; // 無向圖的當前頂點數和邊數  
                      19.  }Graph;  

                      圖的遍歷

                          圖的遍歷比樹的遍歷要復雜的多,因為圖的任一頂點都有可能與其他的頂點相鄰接,因此,我們需要設置一個輔助數組visited[]來標記某個節點是否已經被訪問過。圖的遍歷通常有兩種方法:深度優先遍歷(BFS)和廣度優先遍歷(DFS),兩種遍歷方式的思想都不難理解。下面我們就以如下圖所示的例子來說明圖的這兩種遍歷方式的基本思想,并用鄰接表作為圖的存儲結構,給出BFS和DFS的實現代碼(下圖為無向圖,有向圖的BFS和DFS實現代碼與無向圖的相同):

                          我們以鄰接表作為上圖的存儲結構,并將A、B、C、D、E、F、G、H在頂點數組中的序號分別設為0、1、2、3、4、5、6、7。我們根據上圖所包含的信息,精簡了鄰接表的存儲結構,采取如下所示的結構來存儲圖中頂點和邊的相關信息:

                      1. #define NUM 8          //圖中頂點的個數  
                      2.   
                      3. /* 
                      4. 用鄰接表作為圖的存儲結構 
                      5. 在鄰接表中,用一個一維數組存儲圖中的每個頂點的信息, 
                      6. 同時為每個頂點建立一個單鏈表,鏈表中的節點保存依附在該頂點上的邊或弧的信息 
                      7. */  
                      8. typedef struct node  
                      9. {   //鏈表中的每個節點,保存依附在該節點上的邊或弧的信息  
                      10.     int vertex;          //在有向圖中表示該弧所指向的頂點(即弧頭)的位置,  
                      11.                          //在無向圖中表示依附在該邊上的另一個頂點的位置  
                      12.     struct node *pNext;  //指向下一條依附在該頂點上的弧或邊  
                      13. }Node;  
                      14. typedef struct head  
                      15. {   //數組中的每個元素,保存圖中每個頂點的相關信息  
                      16.     char data;          //頂點的數據域  
                      17.     Node *first;        //在有向圖中,指向以該頂點為弧尾的第一條弧  
                      18.                         //在無向圖中,指向依附在該頂點上的第一條邊  
                      19. }Head,*Graph;           //動態分配數組保存每個頂點的相關信息  

                          那么用鄰接表來表示上圖中各頂點間的關系,如下圖所示:

                          深度優先搜索

                          深度優先搜索(DFS)類似于樹的先序遍歷(如尚未掌握圖的先序遍歷,請移步這里:http://blog.csdn.net/ns_code/article/details/12977901)。其基本思想是:從圖中某個頂點v出發,遍歷該頂點,而后依次從v的未被訪問的鄰接點出發深度優先遍歷圖中,直到圖中所有與v連通的頂點都已被遍歷。如果當前圖只是需要遍歷的非連通圖的一個極大連通子圖,則另選其他子圖中的一個頂點,重復上述遍歷過程,直到該非連通圖中的所有頂點都被遍歷完。很明顯,這里要用到遞歸的思想。

                          結合上面的例子來分析,假設從A點開始遍歷該圖,根據圖中頂點的存儲關系,會按照下面的步驟來遍歷該圖:

                          1、在訪問完頂點A后,選擇A的第一個鄰接點B進行訪問;

                          2、而后看B的鄰接點,由于B的第一個鄰接點A已經被訪問過,故選擇其下一個鄰接點D進行訪問;

                          3、而后看D的鄰接點,由于D的第一個鄰接點B已經被訪問過,故選擇其下一個鄰接點H進行訪問;

                          4、而后看H的鄰接點,由于H的第一個鄰接點D已經被訪問過,故選擇其下一個鄰接點E進行訪問;

                          5、而后看E的鄰接點,由于E的第一個鄰接點B已經被訪問過,那么看其第二個鄰接點H,也被訪問過了,E的鄰接點已經全部被訪問過了。

                          6、這時退回到上一層遞歸,回到頂點H,同樣H的鄰接點也都被訪問完畢,再退回到D,D的鄰接點也已訪問完畢,再退回到B,一直退回到A;

                          7、由于A的下一個鄰接點C還沒有被訪問,因此訪問C;

                          8、而后看C的鄰接點,由于C的第一個鄰接點A已經被訪問過,故選擇其下一個鄰接點F進行訪問;

                          9、而后看F的鄰接點,由于F的第一個鄰接點C已經被訪問過,故選擇其下一個鄰接點G進行訪問;

                          10、而后看G的鄰接點,由于G的臨界點都已被訪問完畢,因此會退到上一層遞歸,看F頂點;

                          11、同理,由F再回退到C,再由C回退到A,這是第一層的遞歸,A的所有鄰接點也已都被訪問完畢,遍歷到此結束。



                      酷斃

                      雷人

                      鮮花

                      雞蛋

                      漂亮
                      • 快畢業了,沒工作經驗,
                        找份工作好難啊?
                        趕緊去人才芯片公司磨練吧!!

                      最新評論

                      關于LUPA|人才芯片工程|人才招聘|LUPA認證|LUPA教育|LUPA開源社區 ( 浙B2-20090187  

                      返回頂部
                      双色球中奖图片

                                                              想学吉林时时 江苏七位数18037期 能挣钱的棋牌app排行榜 30选5开奖结果湖北 快速时时 扑克21策略 全天云南时时彩计划 幸运时时彩基本走势图 陕西十一选五基本走势图 吉林省十一选五前一走势图