內容預覽

零、讀前說明
一、概述
二、深度優先遍歷（DFS）
- 2.1、無向圖的遍歷程序
- 2.2、有向圖的遍歷程序
- 2.3、總結說明
- 2.4、實作源代碼
三、廣度優先遍歷（BFS）
- 3.1、廣度優先的遍歷程序
- 3.2、總結說明
- 3.3、實作源代碼
四、原始碼測驗效果
- 4.1、測驗案例原始碼
- 4.2、測驗效果圖
五、簡單的總結

零、讀前說明

本文中所有設計的代碼均通過測驗，并且在功能性方面均實作應有的功能，
設計的代碼并非全部公開，部分無關緊要代碼并沒有貼出來，
如果你也對此感興趣、也想測驗原始碼的話，可以私聊我，非常歡迎一起探討學習，
由于時間、水平、精力有限，文中難免會出現不準確、甚至錯誤的地方，也很歡迎大佬看見的話批評指正，
時隔三個月，我終于回來了，嘻嘻，，，，，，，，，，，，收！

摘要

??圖是一種非線性的資料結構，圖的遍歷指的是 從圖中的某一頂點出發，沿著一些邊訪問圖中所有的頂點，使得每個頂點都被訪問且僅被訪問一次，根據遍歷路徑的不同，通常有兩種遍歷圖的方法：深度優先遍歷(Depth First Search )和廣度優先遍歷(Breadth First Search )，它們對無向圖和有向圖都適用，圖的遍歷演算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等演算法的基礎，

一、概述

??由于圖結構本身的復雜性，所以圖的遍歷操作也較復雜，主要表現在以下四個方面：

??① 在圖結構中，沒有一個 “自然” 的首結點，圖中任意一個頂點都可作為第一個被訪問的結點，
??② 在非連通圖中，從一個頂點出發，只能夠訪問它所在的連通分量上的所有頂點，因此，還需考慮如何選取下一個出發點以訪問圖中其余的連通分量，
??③ 在圖結構中，如果有回路存在，且圖中的任意一個頂點可能與其他頂點相通，那么一個頂點被訪問之后，有可能沿回路又回到該頂點，
??④ 在圖結構中，一個頂點可以和其它多個頂點相連，當這樣的頂點訪問過后，存在如何選取下一個要訪問的頂點的問題，

??所以在進行圖的遍歷程序中，一般情況下，對于上述的問題：

??1 、遍歷開始，一般 隨機選擇一個頂點作為起始頂點
??2 、對于非連通圖，一般都是 進行多次呼叫遍歷演算法（ n n n 個非連通圖需要呼叫 n n n 次遍歷演算法）
??3 、圖中可能存在回路，所以 設定訪問標志陣列 visted[ n n n]（ n n n 為頂點的個數），用來表示每個被訪問的頂點，
??4 、一般情況下采用 深度優先遍歷 和 廣度優先遍歷

??圖的遍歷可分為四類：

????遍歷完所有的邊而不能有重復，即所謂“一筆畫問題”或“歐拉路徑”；
????遍歷完所有的頂點而沒有重復，即所謂“哈密爾頓問題”；
????遍歷完所有的邊而可以有重復，即所謂“中國郵遞員問題”；
????遍歷完所有的頂點而可以重復，即所謂“旅行推銷員問題”，

??那么下面開始深度優先遍歷（DFS）、廣度優先遍歷（BFS）的程序說明，

二、深度優先遍歷（DFS）

2.1、無向圖的遍歷程序

??首先來看看 無向圖遍歷的程序說明，以下圖為例，

圖2.1 無向圖遍歷的程序示意圖 ??

??根據圖例，我們可以畫出此圖的簡單的鄰接矩陣，以下圖為例，

圖2.2 無向圖鄰接矩陣示意圖 ??

??1、假設訪問起始遍歷的頂點為頂點 A（圖 2.1中 1 所指），同時標記為已訪問（下同，不再贅述）；
??2、然后開始訪問頂點 A 的鄰接點（分別為頂點 B 、頂點 C 、頂點 D（對應于上圖 2.2中的第 0 行，即頂點 A的鄰接點），（遍歷規則設定為 按照頂點的編號小的優先，即先小后大，其實鄰接矩陣的遍歷順序也是按照編號進行從小到大的依次遍歷）），所以首先進行遍歷頂點 B（圖 2.1中 2 所指，對應于上圖 2.2中的第 1 行）， B 為第一次訪問，然后再繼續遍歷頂點 C（圖 2.1中 3 所指對應于上圖 2.2中的第 3 行）且頂點 C為第一次訪問，然后遍歷頂點 C 的鄰接點；
??3、從圖 2.1中可以看出，頂點 C 的鄰接點為頂點 A 和頂點 B ，經判斷頂點 A 已經被訪問，所以需要回退到頂點 B （圖 2.1中 4 所指），然后繼續遍歷頂點 B 的的鄰接點（頂點 E ，頂點 F ）；
??4、按照編號小的優先原則，繼續遍歷頂點 E （圖 2.1中 5 所指，對應于上圖 2.2中的第 5 行），然后再繼續遍歷頂點 D（圖 2.1中 6 所指，對應于上圖 2.2中的第 4 行），同理 D 的鄰接點（頂點 A 、頂點 D ）均已經被訪問，再回退到頂點 B （圖 2.1中 7、8 所指），繼續遍歷頂點 B 的鄰接點頂點 F（圖 2.1中 9 所指，對應于上圖 2.2中的第 6 行）；
??5、頂點 F 沒有后續鄰接點，遍歷完成，按照圖 2.1中 10、11 所指回退到起始位置，至此遍歷完成，

??所以遍歷的順序為： A -> B -> C -> E -> D -> F

2.2、有向圖的遍歷程序

??來看看 有向圖遍歷的程序說明，以下圖為例，

圖2.3 有向圖遍歷的程序示意圖 ??

??根據圖例，我們可以畫出此圖的簡單的鄰接矩陣，以下圖為例，

圖2.4 有向圖鄰接矩陣示意圖 ??

??有向圖遍歷的程序說明：

??1、假設訪問起始遍歷的頂點為頂點 A（圖中 1 所指），同時標記為已訪問（下同，不再贅述）；
??2、然后開始訪問頂點 A 的鄰接點（分別為頂點 B 、頂點 C 、頂點 D ，（遍歷規則設定為 按照頂點的編號小的優先，即先小后大，其實鄰接矩陣的遍歷順序也是按照編號進行從小到大的依次遍歷）），所以首先進行遍歷頂點 B（圖中 2 所指）， B 為第一次訪問，然后再繼續遍歷頂點 B 的鄰接點（頂點 E ，頂點 F ），按照編號小的優先原則，遍歷頂點 E （圖中 3 所指）且頂點 E為第一次訪問，然后遍歷頂點 E 的鄰接點，頂點 E 沒有鄰接點，所以進行回退操作，回退到頂點 B ，然后遍歷頂點 F （圖中 5 所指）；
??3、然后繼續遍歷頂點 F 的鄰接點，沒有鄰接點則開始回退（圖中 6、7 所指）到頂點 A ，繼續遍歷頂點 A 的編號較小的沒有被訪問的鄰接點 C ，然后遍歷 C 的鄰接點（頂點 B ），經判斷頂點 B 已經被訪問過，所以開始回退（圖中 9 所指）到頂點 A ；
??4、繼續遍歷頂點 A 的編號較小的沒有被訪問的鄰接點頂點 D （圖中 10 所指），然后遍歷頂點 D 的鄰接點（頂點 E ），經判斷頂點 E 已經被訪問，然后繼續回退到頂點 A（圖中 11 所指）；
??5、至此則所有頂點遍歷完成，

??所以遍歷的順序為： A -> B -> E -> F -> C -> D

2.3、總結說明

??綜合上述的程序說明，可以總結出來 深度優先遍歷 的演算法描述（類似于二叉樹的先序遍歷）：

??1、訪問起始頂點 v v v；
??2、當 v v v 存在鄰接點并且此鄰接點未被訪問過時，繼續深度遍歷其未被訪問過的鄰接頂點 w w w；
??3、當 v v v 的所有鄰接頂點都被訪問過：
????1）如果圖中所有頂點均已被訪問，則演算法結束；
????2）如果圖中還有未被訪問的頂點（非連通圖）、以未訪問頂點作為起始頂點繼續深度遍歷，

2.4、實作源代碼

??實作代碼中已經有了比較詳細的注釋，所以便不再進行說明，代碼如下所示，

/**
 * 功 能：
 *      深度優先遍歷圖的輔助函式 -- 遞回實作
 * 參 數：
 *      graph：要遍歷的圖
 *      v    ： 起始遍歷的節點（在節點組中的編號/下標）
 *      visited ：是否被訪問的標識
 * 回傳值：
 *      無 
 **/
static void recursive_dfs(TMGraph *graph, int v, int visited[])
{
    int i = 0;
    if (graph == NULL || v < 0 || visited == NULL)
        goto END;

    // 列印輸出節點資訊，也可以其它操作
    printf("%s ", (char *)(graph->vertex[v]));
    // 設定訪問的標志
    visited[v] = TRUE;

    for (i = 0; i < graph->count; i++)
    {
        // 判斷與v相鄰的節點i之間是否存在邊（等于0不存在，存在的變的話既可以是1，
        // 也可使權值(1也有可能為權值)），并且是否已經被訪問
        if ((graph->matrix[v][i] != 0) && visited[i] == FALSE)
        {
            // 繼續遞回遍歷
            recursive_dfs(graph, i, visited);
        }
    }
END:
    return;
}

/**
 * 功 能：
 *      深度優先遍歷圖的函式
 * 參 數：
 *      graph：要遍歷的圖
 *      v    ： 起始遍歷的節點（在節點組中的編號/下標） 
 * 回傳值：
 *      無 
 **/
int MGraph_DFS(MGraph *graph, int v)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int *visited = NULL;
    int ret = -1;

    if (tGraph == NULL || v < 0 || v > tGraph->count)
        goto ERROR;

    // 為訪問的標志申請空間并初始化
    visited = (int *)calloc(tGraph->count, sizeof(int));
    if (visited == NULL)
        goto ERROR;

    recursive_dfs(tGraph, v, visited); // 開始遞回遍歷

    // 再次遍歷所有節點，如果在上次訪問中有沒有被訪問的節點（沒有邊連接），非連通圖，那么以此節點開始繼續訪問
    for (int i = 0; i < tGraph->count; i++)
    {
        if (visited[i] == FALSE) // 判斷是否被訪問
        {
            recursive_dfs(tGraph, i, visited); // 對未訪問的鄰接頂點遞回呼叫
        }
    }
    printf("\n");
    ret = 0;
ERROR:
    if (visited)
        free(visited);

    return ret;
}

三、廣度優先遍歷（BFS）

3.1、廣度優先的遍歷程序

??圖中的形式有向圖和無向圖的順序正好重復且一模一樣，所以就在一起描述，以下圖為例，

圖3.1 無向圖遍歷的程序示意圖 ??

??1、假設訪問起始遍歷的頂點為頂點 A，將頂點 A 入佇列（圖中 1 所指），此時佇列中為節點 A；（圖中 1 所指），同時標記為已訪問（下同，不再贅述）；
??2、然后將頂點A出佇列，頂點 A 的遍歷完成，然后開始訪問頂點 A 的鄰接點（分別為頂點 B 、頂點 C 、頂點 D ，（遍歷規則設定為 按照頂點的編號小的優先，即先小后大，其實鄰接矩陣的遍歷順序也是按照編號進行從小到大的依次遍歷））；
??3、然后將頂點 A 的所有的沒有被訪問的鄰接點入佇列（入佇列順序從編號小到大依次為頂點 B、頂點 C、頂點 D，圖中 2、3、4 所指），此時佇列中為頂點 B、C、D；
??4、然后將頂點 B 出佇列（圖中 5 所指），頂點 B 的遍歷完成，然后將頂點 B 的所有的沒有被訪問的鄰接點入佇列（入佇列的順序為 E、F ，圖中 6、7 所指），此時佇列中的節頂點為 C、D、E、F ；
??5、然后將頂點 C 出佇列（圖中 8 所指），頂點 C 的遍歷完成，然后將頂點 C 的所有的沒有被訪問的鄰接點入佇列（其鄰接點為頂點 B 和頂點 A （圖中有向圖沒有頂點 A ），但是頂點 B 經判斷已經遍歷），則不再入佇列，此時佇列中的頂點為 D、E、F ；
??6、然后將頂點 D 出佇列（圖中 9 所指），頂點 D 的遍歷完成，此時頂點 D 的鄰接點為頂點 E 和頂點 A （圖中有向圖沒有頂點 A ），且經判斷頂點 E 已經被訪問所以不再入佇列，此時佇列中的頂點為 E、F；
??7、繼續出佇列為頂點 E （圖中 10 所指），有向圖中頂點 E 沒有鄰接點，無向圖中鄰接點為 B 和 D ，經判斷均已經被訪問，所以也不再入佇列；此時佇列中頂點為 F ；
??8、出佇列頂點 F （圖中 11 所指），經判斷頂點 F 的所有鄰接點均已經被訪問，沒有可入佇列的頂點，此時佇列為空，遍歷完成，

??所以，遍歷的順序為： A -> B -> C -> D -> E -> F

3.2、總結說明

??綜合上述的程序說明，可以總結出來 廣度優先遍歷 的演算法描述（二叉樹的層序遍歷）：

??1、訪問起始頂點 v 0 v_0 v0?；
??2、依次訪問 v 0 v_0 v0? 的各個鄰接點 v 0 v_0 v0? 1 _1 1?， v 0 v_0 v0? 2 _2 2? ，…， v 0 v_0 v0? x _x x?；
??3、假設最近一次訪問的頂點依次為 v i v_i vi? 1 _1 1?， v i v_i vi? 2 _2 2?， …， v i v_i vi? y _y y?，則依次訪問 v i v_i vi? 1 _1 1?， v i v_i vi? 2 _2 2?， …， v i v_i vi? y _y y? 的未被訪問的鄰接點；
??4、重復3，直到所有頂點均被訪問，

3.3、實作源代碼

??實作代碼中已經有了比較詳細的注釋，所以便不再進行說明，代碼如下所示，

/**
 * 功 能：
 *      廣度優先遍歷圖的輔助函式 -- 佇列實作
 * 參 數：
 *      graph：要遍歷的圖
 *      v    ： 起始遍歷的節點（在節點組中的編號/下標）
 *      visited ：是否被訪問的標識
 * 回傳值：
 *      無 
 **/
static void bfs(TMGraph *graph, int v, int visited[])
{
    LinkQueue *queue = NULL;
    if (graph == NULL || v < 0 || visited == NULL)
        goto ERROR;

    // 創建一個佇列
    queue = fLinkQueue.create();
    if (queue == NULL)
        goto ERROR;

    // 入佇列
    fLinkQueue.enqueue(queue, graph->vertex + v);

    visited[v] = 1;

    while (fLinkQueue.length(queue) > 0)
    {
        v = (MVertex **)fLinkQueue.dequeue(queue) - graph->vertex;

        printf("%s ", (char *)(graph->vertex[v]));

        for (int i = 0; i < graph->count; i++) // 對每一個頂點做回圈
        {
            // 判斷與v相鄰的節點i之間是否存在邊，并且是否已經被訪問
            if ((graph->matrix[v][i] != 0) && visited[i] == FALSE)
            {
                // 入佇列
                fLinkQueue.enqueue(queue, graph->vertex + i);
                visited[i] = TRUE; // 將找到的此頂點標記為已訪問
            }
        }
    }

ERROR:

    if (queue)
        fLinkQueue.destroy(queue); // 銷毀佇列
    return;
}

/**
 * 功 能：
 *      廣度優先遍歷圖的函式
 * 參 數：
 *      graph：要遍歷的圖
 *      v    ： 起始遍歷的節點（在節點組中的編號/下標） 
 * 回傳值：
 *      無 
 **/
int MGraph_BFS(MGraph *graph, int v)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int *visited = NULL;
    int ret = -1;

    if (tGraph == NULL || v < 0 || v > tGraph->count)
        goto ERROR;

    // 為訪問的標志申請空間并初始化
    visited = (int *)calloc(tGraph->count, sizeof(int));
    if (visited == NULL)
        goto ERROR;

    bfs(tGraph, v, visited);

    // 再次遍歷所有節點，如果在上次訪問中有沒有被訪問的節點（沒有邊連接），非連通圖，那么以此節點開始繼續訪問
    for (int i = 0; i < tGraph->count; i++)
    {
        // 判斷頂點是否曾經訪問過，沒有訪問過則繼續訪問
        if (visited[i] == FALSE)
        {
            bfs(tGraph, i, visited); // 遞回遍歷
        }
    }
    printf("\n");
    ret = 0;
ERROR:
    if (visited)
        free(visited);
    return ret;
}

四、原始碼測驗效果

4.1、測驗案例原始碼

??根據上述深度優先遍歷以及廣度優先遍歷的程序說明等，撰寫出相關的測驗案例的實作代碼，原始碼如下所示，

#include "../src/graph/graph.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int ret = system("color "); // 顏色設定，用于在windows下終端顯示的時候不明原因換行的問題
    // 頂點
    MVertex const *v[] = {"A", "B", "C", "D", "E", "F"};

    /** 下面開始無向圖的測驗 **/
    printf("\n\e[1;31mLet's start with an example of an undirected graph:\e[0m\n");

    // 創建一個圖
    MGraph *ungraph = funMGraph.create((MVertex **)v, 6);

    // 添加邊
    ret = funMGraph.edge.add(ungraph, 0, 1, 1, UNDIRECTED_GRAPH); // (A, B)
    ret = funMGraph.edge.add(ungraph, 0, 2, 1, UNDIRECTED_GRAPH); // (A, C)
    ret = funMGraph.edge.add(ungraph, 0, 3, 1, UNDIRECTED_GRAPH); // (A, D)
    ret = funMGraph.edge.add(ungraph, 1, 5, 1, UNDIRECTED_GRAPH); // (B, F)
    ret = funMGraph.edge.add(ungraph, 1, 4, 1, UNDIRECTED_GRAPH); // (B, E)
    ret = funMGraph.edge.add(ungraph, 2, 1, 1, UNDIRECTED_GRAPH); // (C, B)
    ret = funMGraph.edge.add(ungraph, 3, 4, 8, UNDIRECTED_GRAPH); // (D, E)

    // 顯示
    funMGraph.display(ungraph);

    // 遍歷
    printf("\nDFS Starting with vertex 'A': ");
    ret = funMGraph.traverse.dfs(ungraph, 0);
    printf("BFS Starting with vertex 'A': ");
    ret = funMGraph.traverse.bfs(ungraph, 0);

    printf("DFS Starting with vertex 'C': ");
    ret = funMGraph.traverse.dfs(ungraph, 2);
    printf("BFS Starting with vertex 'D': ");
    ret = funMGraph.traverse.bfs(ungraph, 3);

    printf("\n\e[1;31mLet's start with an example of directed graph \e[0m\n");
    // 創建一個圖
    MGraph *graph = funMGraph.create((MVertex **)v, 6);

    // 添加邊
    ret = funMGraph.edge.add(graph, 0, 1, 1, DIRECTED_GRAPH); // <A, B>
    ret = funMGraph.edge.add(graph, 0, 2, 1, DIRECTED_GRAPH); // <A, C>
    ret = funMGraph.edge.add(graph, 0, 3, 1, DIRECTED_GRAPH); // <A, D>
    ret = funMGraph.edge.add(graph, 1, 5, 1, DIRECTED_GRAPH); // <B, F>
    ret = funMGraph.edge.add(graph, 1, 4, 1, DIRECTED_GRAPH); // <B, E>
    ret = funMGraph.edge.add(graph, 2, 1, 1, DIRECTED_GRAPH); // <C, B>
    ret = funMGraph.edge.add(graph, 3, 4, 8, DIRECTED_GRAPH); // <D, E>

    // 顯示
    funMGraph.display(graph);

    // 遍歷
    printf("\nDFS Starting with vertex 'A': ");
    ret = funMGraph.traverse.dfs(graph, 0);
    printf("BFS Starting with vertex 'A': ");
    ret = funMGraph.traverse.bfs(graph, 0);

    printf("DFS Starting with vertex 'C': ");
    ret = funMGraph.traverse.dfs(ungraph, 2);
    printf("BFS Starting with vertex 'D': ");
    ret = funMGraph.traverse.bfs(ungraph, 3);

    // 銷毀圖
    funMGraph.destroy(graph);
    funMGraph.destroy(ungraph);

    printf("\n\e[1;32msystem exited with return code %d\e[0m\n\n", 0);

    return ret;
}

4.2、測驗效果圖

??根據上述測驗代碼，進行編譯并測驗效果以如下圖所示，

圖4.1 無向圖遍歷的程序示意圖 ??

五、簡單的總結

??遍歷的實質：找到每個頂點的鄰接點的程序，

??深度優先遍歷 ：一條道路走到黑的故事，是一個遞回的定義，也是一個俄羅斯套娃的程序，

????對于深度優先遍歷，在遍歷到有多個鄰接點的位置的時候，不同的選擇將會出現不同的遍歷順序，

????鄰接矩陣：如果設定了存盤結構為鄰接矩陣，那么基于鄰接矩陣的遍歷的順序是固定的

??廣度優先遍歷 ：wifi信號式的遍歷，

????對于 廣度優先遍歷，甚至于所有的層序的遍歷，都需要借助佇列的輔助實作

??
??好啦，廢話不多說，總結寫作不易，如果你喜歡這篇文章或者對你有用，請動動你發財的小手手幫忙點個贊，當然 關注一波 那就更好了，有任何問題或者想法，歡迎 留言評論，就到這兒了，么么噠(* ￣3)(ε￣ *)，

上一篇：資料結構（廿四） – C語言版 – 圖 - 圖的存盤結構 – 十字鏈表、鄰接多重表、邊集陣列
下一篇：資料結構（廿六） – C語言版 – 圖 - 圖的遍歷 – 鄰接表 - 深度/廣度優先遍歷/搜索（DFS、BFS）

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231979.html

標籤：AI

上一篇：Java高頻面試題及答案整理（2021年最新版）

下一篇：想做技術自媒體實作財富自由？先看看廣告報價吧，無編碼學爬蟲之二。

資料結構（廿五） -- C語言版 -- 圖 - 圖的遍歷 -- 鄰接矩陣 - 深度/廣度優先遍歷/搜索（DFS、BFS）