零、讀前說明

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

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

??書接前文，如果需要查看圖的遍歷的基礎知識或者鄰接矩陣的相關知識，請移步博文：

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

??所以本次接下來直接進入到 基于鄰接表 的圖的 深度優先遍歷 和 廣度優先遍歷，

一、深度優先遍歷

1.1、深度優先的遍歷程序

??下面開始開始說明無向圖的深度優先遍歷的程序，其實有向圖的深度遍歷與無向圖的深度優先遍歷一致（唯一不同的就是兩個頂點有連線但是不一定是鄰接的關系，所以不再進行贅述），

??以下圖為例，對于同一種圖的結構進行無向圖和有向圖的分別表示描述（一無向圖的為主，有向圖的可以參考無向圖的描述，基本上一致），

?

??同上圖，我們可以根據圖例畫出對應圖的 鄰接表 表示形式，如下圖所示，

??
??1、假設訪問起始遍歷的頂點為頂點 A（圖中 1 所指），同時標記為已訪問（下同，不再描述）；
??2、然后開始訪問頂點 A 的鄰接點，也就是開始訪問頂點 B、頂點 C 或者頂點 D（我們在鄰接表的增加邊的時候鏈表采用的是頭插入，所以后出現（頂點編號大的）的邊在鄰接鏈表的前部，在遍歷的時候根據鏈表的順序進行遍歷），所以接下來應該遍歷頂點 D（圖中 2 所指），然后遍歷頂點 D的鄰接點 E（圖中 3 所指）；
??3、然后開始遍歷頂點 E 的鄰接點頂點 B（圖中 4 所指）（在有向圖中頂點 E 沒有鄰接點，所以將按照上述右邊圖所示標識進行后續的遍歷，后續不在進行贅述）；
??4、由圖中可以看出來，頂點 B 有兩個鄰接點，分別為頂點 A 和頂點 C，根據鏈接表中鏈表順序，應該訪問的頂點 D（圖中 5 所指），然后繼續訪問 C 的鄰接點，為頂點 A（圖中淡色線條所指），經判斷頂點 A 已經標記為已訪問，所以開始回退（圖中 6 所示）到頂點 B；
??5、繼續遍歷頂點 B 的鄰接點頂點 A（圖中淡色線條所指），經判斷頂點 A 已經標記為已訪問不需要再遍歷，繼續遍歷頂點 B 的鄰接點頂點 F（圖中 7 所指）；
??6、至此，所有頂點均遍歷完成，然后依次回傳到最初訪問的頂點位置（圖中 8、9、10、11 所指），遍歷演算法結束，

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

1.2、深度優先的遍歷實作代碼

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

/**
 * 功 能：
 *      深度優先遍歷圖的輔助函式 -- 遞回實作
 * 參 數：
 *      graph：要遍歷的圖
 *      v    ： 起始遍歷的節點（在節點組中的編號/下標）
 *      visited ：是否被訪問的標識
 * 回傳值：
 *      無
 **/
static void recursive_dfs(TLGraph *graph, int v, int visited[])
{
    int i = 0;
    if (graph == NULL || v < 0 || visited == NULL)
        return;
        
    // 列印輸出節點資訊，也可以其它操作
    printf("%s ", (char *)graph->vertex[v]);
    // 設定訪問的標志
    visited[v] = TRUE;
    // 回圈獲取所有的鄰接節點
    for (i = 0; i < funLinkList.length(graph->first[v]); i++)
    {
        // 獲取到當前節點
        TListNode *node = (TListNode *)funLinkList.get(graph->first[v], i);
        // 判斷是否訪問過，沒有則繼續訪問
        if (visited[node->adjvex] == FALSE)
        {
            // 遞回遍歷訪問
            recursive_dfs(graph, node->adjvex, visited);
        }
    }
}

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

    if (graph == NULL)  goto ERROR;

    tGraph = (TLGraph *)graph;

    if ((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");
    free(visited);

    return 0;
ERROR:
    return -1;
}

二、廣度優先遍歷

2.1、廣度優先的遍歷程序

??圖中的形式有向圖和無向圖的順序相差不大，所以就在一起描述，以下圖為例，

??
??1、假設訪問起始遍歷的頂點為頂點 A，將頂點 A 入佇列（圖中 1 所指，入佇列也是為了在訪問完其中某個鄰接點的后再訪問其他鄰接點），此時佇列中為節點 A；（圖中 1 所指），同時標記為已訪問（下同，不再贅述）；
??2、然后將頂點 A 出佇列，頂點 A 的遍歷完成，然后開始訪問頂點 A 的鄰接點（分別為頂點 B 、頂點 C 、頂點 D ，（由于是按照鄰接表進行遍歷，并且鏈表采用的時候頭插入方式，所以后插入的節點在鏈表的前面，所以遍歷規則設定為 按照鏈表的節點的順序進行遍歷，如果插入鏈表的位置不同，那么遍歷的結果也不同））；
??3、然后將頂點 A 的所有的沒有被訪問的鄰接點入佇列（入佇列順序從前到后依次為頂點 D、頂點 C、頂點 B，圖中 2、4、6 所指），此時佇列中為頂點 B、C、D；
??4、然后將頂點 D 出佇列（圖中 2 所指），頂點 D 的遍歷完成，然后將頂點 D 的所有的沒有被訪問的鄰接點入佇列（入佇列的順序為 E、A（由于 A 已經被訪問，所以不再入佇列），圖中 8 所指），此時佇列中的節頂點為 C、B、E ；
??5、然后將頂點 C 出佇列（圖中 4 所指），頂點 C 的遍歷完成，然后將頂點 C 的所有的沒有被訪問的鄰接點入佇列（其鄰接點為頂點 B 和頂點 A （圖中有向圖沒有頂點 A ），但是頂點 A、B 經判斷已經被訪問），則不再入佇列，此時佇列中的頂點為 B、E ；
??6、然后將頂點 D 出佇列（圖中 6 所指），頂點 B 的遍歷完成，此時頂點 B 的鄰接點為頂點 A 、頂點 C、頂點 E、頂點 F （圖中有向圖沒有頂點 A、C ），且經判斷頂點 A、C、E 已經被訪問所以不再入佇列，此時佇列中的頂點為 E、F；
??7、繼續出佇列為頂點 E （圖中 8 所指），有向圖中頂點 E 沒有鄰接點，無向圖中鄰接點為 B 和 D ，經判斷均已經被訪問，所以也不再入佇列；此時佇列中頂點為 F ；
??8、出佇列頂點 F （圖中 10 所指），經判斷頂點 F 的所有鄰接點均已經被訪問，沒有可入佇列的頂點，此時佇列為空，遍歷完成，

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

2.2、廣度優先的遍歷實作代碼

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

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

    // v是下標，直接入佇列當前節點（從graph->vertex偏移v個量的）的地址
    fLinkQueue.enqueue(queue, graph->vertex + v);
    // 設定當前節點的訪問標志
    visited[v] = TRUE;

    // 回圈讀取鏈表中的所有節點
    while (fLinkQueue.length(queue) > 0)
    {
        // 出佇列當前節點，和前面接如佇列相反操作，獲取到下標的值（偏移量）
        v = (LVertex **)fLinkQueue.dequeue(queue) - graph->vertex;
        // 輸出節點資訊
        printf("%s ", (char *)graph->vertex[v]);
        // 遍歷與它對應的鄰接鏈表，遍歷與此節點有關聯的下一層的節點
        for (int i = 0; i < funLinkList.length(graph->first[v]); i++)
        {
            // 獲取鄰接點表中的每一個節點
            TListNode *node = (TListNode *)funLinkList.get(graph->first[v], i);
            // 判斷訪問的標志
            if (visited[node->adjvex] == FALSE)
            {
                // 入佇列
                fLinkQueue.enqueue(queue, graph->vertex + node->adjvex);
                // 將找到的此頂點標記為已訪問
                visited[node->adjvex] = TRUE;
            }
        }
    }
    // 銷毀佇列
    fLinkQueue.destroy(queue);
}

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

    if (graph == NULL) goto ERROR;

    tGraph = (TLGraph *)graph;

    if ((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");
    free(visited);

    return 0;
ERROR:
    return -1;
}

三、原始碼測驗效果

3.1、測驗案例原始碼

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

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

int main(int argc, char *argv[])
{
    system("color "); // 顏色設定，用于在windows下終端顯示的時候不明原因換行的問題

    printf("\n\e[1;31mLet's start with an example of undirected graph:\e[0m\n");

    LVertex const *v[] = {"A", "B", "C", "D", "E", "F"};
    LGraph *ungraph = funGraph.create((LVertex **)v, 6);

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

    // 顯示
    funGraph.display(ungraph, FLAG_NOTDISPLAY_HINT);

    // 遍歷 
    printf("DFS Start with vertex 'A': ");
    funGraph.traverse.dfs(ungraph, 0);
    printf("BFS Start with vertex 'A': ");
    funGraph.traverse.bfs(ungraph, 0);
    printf("DFS Start with vertex 'C': ");
    funGraph.traverse.dfs(ungraph, 2);
    printf("BFS Start with vertex 'C': ");
    funGraph.traverse.bfs(ungraph, 2);
    printf("BFS Start with vertex 'E': ");
    funGraph.traverse.dfs(ungraph, 4);
    printf("BFS Start with vertex 'D': ");
    funGraph.traverse.bfs(ungraph, 3);

    printf("\n\e[1;31mLet's start with an example of directed graph:\e[0m\n");

    LGraph *graph = funGraph.create((LVertex **)v, 6);

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

    // 顯示
    funGraph.display(graph, FLAG_NOTDISPLAY_HINT);
    // 遍歷 
    printf("DFS Start with vertex 'A': ");
    funGraph.traverse.dfs(ungraph, 0);
    printf("BFS Start with vertex 'A': ");
    funGraph.traverse.bfs(ungraph, 0);
    printf("DFS Start with vertex 'C': ");
    funGraph.traverse.dfs(ungraph, 2);
    printf("BFS Start with vertex 'C': ");
    funGraph.traverse.bfs(ungraph, 2);
    printf("BFS Start with vertex 'E': ");
    funGraph.traverse.dfs(ungraph, 4);
    printf("BFS Start with vertex 'D': ");
    funGraph.traverse.bfs(ungraph, 3);

    // 銷毀
    funGraph.destroy(ungraph);
    funGraph.destroy(graph);

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

    return 0;
}

3.2、測驗效果圖

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

四、簡單的總結

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

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

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

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

????鄰接表：如果設定了存盤結構為鄰接表，那么不同的鏈表順序也將導致有不同的遍歷的順序

????對于 稠密圖 ：適合在 鄰接矩陣 上進行 深度優先遍歷

????對于 稀疏圖 ：適合在 鄰接表 上進行 深度優先遍歷

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

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

??
??最近由于作業、專案各種事情、加上本身冬天手冷腳冷心更冷、身體也不好了，腦袋也不好了、心情就更加不好了，所以更新可以說狠狠狠緩慢，并且在寫作程序中明顯有點力不從心的感覺了，最近又有很多事情一個比一個要人命的感覺，本來資料結構后面的部分用的比較少，所以暫時就不再更新 資料結構 部分的內容，如果后續用到或者有比較寬松的時間的話會繼續學習并且同時繼續更新相關內容，
??資料結構部分的內容基本上從開始更新到目前為止快要一年的時間了，到目前為止才基本上寫完資料結構最基礎的部分內容，非常感謝閱讀并給我鼓勵的讀著大大們，你們的支持是我最大的動力，希望大佬們繼續能夠支持我！！！O(∩_∩)O哈哈~
??
??好啦，廢話不多說，總結寫作不易，如果你喜歡這篇文章或者對你有用，請動動你發財的小手手幫忙點個贊，當然 關注一波 那就更好了，就到這兒了，么么噠(* ￣3)(ε￣ *)，

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