bfs和dfs的應用實例分析

本篇文章給大家分享的是有關bfs和dfs的應用實例分析，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

廣度優先搜索應用舉例：計算網絡跳數

圖結構在解決許多網絡相關的問題時直到了重要的作用。

比如，用來確定在互聯網中從一個結點到另一個結點（一個網絡到其他網絡的網關）的最佳路徑。一種建模方法是采用無向圖，其中頂點表示網絡結點，邊代表結點之間的聯接。使用這種模型，可以采用廣度優先搜索來幫助確定結點間的最小跳數。

如圖1所示，該圖代表Internet中的6個網絡結點。以node1作為起點，有不止1條可以通往node4的路徑。<node1,node2,node4>，<node1,node3,node2,node4>，<node1,node3,node5,node4>都是可行的路徑。廣度優先搜索可以確定最短路徑選擇，即<node1,node2,node4>，一共只需要兩跳。

我們以bfs作為廣度優先搜索的函數名（見示例1及示例2）。該函數用來確定互聯網中兩個結點之間的最小跳數。這個函數有3個參數：graph是一個圖，在這個問題中就代表整個網絡；start代表起始的頂點；hops是返回的跳數鏈表。函數bfs會修改圖graph，因此，如果有必要的話在調用該函數前先對圖創建拷貝。另外，hops中返回的是指向graph中實際頂點的指針，因此調用者必須保證只要訪問hops，graph中的存儲空間就必須保持有效。

graph中的每一個頂點都是一個BfsVertex類型的結構體（見示例1），該結構體有3個成員：data是指向圖中頂點的數據域指針，color在搜索過程中維護頂點的顏色，hops維護從起始頂點開始到目標頂點的跳數統計。

match函數是由調用者在初始化graph時作為參數傳遞給graph_init的。match函數應該只對BfsVertex結構體中的data成員進行比較。

bfs函數將按照前面介紹過的廣度優先搜索的方式來計算。為了記錄到達每個頂點的最小跳數，將每個頂點的hop計數設置為與該頂點鄰接的頂點的hop計數加1。對于每個發現的頂點都這樣處理，并將其涂成灰色。每個頂點的顏色和跳數信息都由鄰接表結構鏈表中的BfsVertex來維護。最后，加載hops中所有跳數未被標記為-1的頂點。這些就是從起始頂點可達的頂點。

bfs的時間復雜度為O（V+E），這里V代表圖中的頂點個數，E是邊的個數。這是因為初始化頂點的顏色屬性以及確保起始頂點存在都需要O（V）的運行時間，廣度優先搜索中的循環的復雜度是O（V+E），加載跳數統計鏈表的時間為O（V）。

示例1：廣度優先搜索的頭文件

/*bfs.h*/
#ifndef BFS_H
#define BFS_H

#include "graph.h"
#include "list.h"

/*定義廣度優先搜索中的頂點數據結構*/
typedef struct BfsVertex_
{
    void *data;
    VertexColor color;
    int hops;
}BfsVertex;

/*函數接口定義*/
int bfs(Graph *graph, BfsVertex *start, List *hops);

#endif // BFS_H

 示例2：廣度優先搜索的實現

/*bfs.c*/
#include <stdlib.h>
#include "bfs.h"
#include "graph.h"
#include "list.h"
#include "queue.h"

/*bfs */
int bfs(Graph *graph, BfsVertex *start, List *hops)
{
    Queue     queue;
    AdjList   *adjlist, *clr_adjlist;
    BfsVertex *clr_vertex, *adj_vertex;
    ListElmt  *element, *member;
    
    /*初始化圖中的所有結點為廣度優先結點*/
    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        clr_vertex = ((AdjList *)list_data(element))->vertex;
        if(graph->match(clr_vertex,start))
        {
            /*初始化起始頂點*/
            clr_vertex->color = gray;
            clr_vertex->hops  = 0;
        }
        else
        {
            /*初始化非起始頂點*/
            clr_vertex->color = white;
            clr_vertex->hops = -1;
        }
    }
    /*初始化隊列，并將起始頂點的鄰接表入隊*/
    queue_init(&queue,NULL);
        /*返回起始頂點的鄰接表，存儲到clr_adjlist*/
    if(graph_adjlist(graph,start,&clr_adjlist) != 0)
    {
        queue_destroy(&queue);
        return -1;
    }
        /*將頂點的鄰接表入隊到隊列*/
    if(queue_enqueue(&queue,clr_adjlist) != 0 )
    {
        queue_destroy(&queue);
        return -1;
    }
    
    /*執行廣度優先探索*/
    while(queue_size(&queue) > 0)
    {
        adjlist = queue_peek(&queue);
        
        /*遍歷鄰接表中的每一個頂點*/
        for(member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member))
        {
            adj_vertex = list_data(member);
            
            /*決定下一個鄰接點的顏色*/
            if(graph_adjlist(graph,adj_vertex,&clr_adjlist) != 0)
            {
                queue_destroy(&queue);
                return -1;
            }
            clr_vertex = clr_adjlist->vertex;
            
            /*把白色的頂點標成灰色，并把它的鄰接頂點入隊*/
            if(clr_vertex->color == white)
            {
                clr_vertex->color = gray;
                clr_vertex->hops = ((BfsVertex *)adjlist->vertex)->hops + 1;
                
                if(queue_enqueue(&queue,clr_adjlist) != 0)
                {
                    queue_destroy(&queue);
                    return -1;
                }
            }
        }
        
        /*將當前頂點鄰接表從隊列中移除并涂成黑色*/
        if(queue_dequeue(&queue,(void **)&adjlist) == 0)
        {
            ((BfsVertex *)adjlist->vertex)->color = black;
        }
        else
        {
            queue_destroy(&queue);
            return -1;
        }
    }
    
    queue_destroy(&queue);
    
    /*返回每一個頂點的hop計數到一個鏈表中*/
    list_init(hops,NULL);
    
    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        /*跳過那些沒有被訪問到的節點（hops = -1）*/
        clr_vertex = ((AdjList *)list_data(element))->vertex;
        if(clr_vertex->color != -1)
        {
            if(list_ins_next(hops,list_tail(hops),clr_vertex) != 0)
            {
                list_destroy(hops);
                return -1;
            }
        }
    }
    return 0;
}

 深度優先搜索的應用舉例：拓撲排序

有時候，我們必須根據各種事物間的依賴關系來確定一種可接受的執行順序。比如，在大學里必須滿足一些先決條件才能選的課程，或者一個復雜的項目，其中某個特定的階段必須在其他階段開始之前完成。要為這一類問題建模，可以采用優先級圖，其采用的是有向圖的思路。在優先級圖中，頂點代表任務，而邊代表任務之間的依賴關系。以必須先完成的任務為起點，以依賴于此任務的其他任務為終點，畫一條邊即可。

如下圖所示，它表示7門課程及其先決條件組成的一份課程表：S100沒有先決條件，S200需要S100，S300需要S200和M100，M100沒有先決條件，M200需要M100，M300需要S300和M200，并且S150沒有先決條件同時也不是先決條件。

通過對這些課程執行拓撲排序，深度優先搜索有助于確定出一中可接受的順序。

拓撲排序將頂點排列為有向無環圖，因此所有的邊都是從左到右的方向。正規來說，有向無環圖G=(V,E)的拓撲排序是其頂點的一個線性排序，以便如果G中存在一條邊（u，v），那么線性順序中u出現在v的前面，在許多情況下，滿足此條件的順序有多個。

下面的代碼示例實現了函數dfs，即深度優先搜索。該函數在這里用來對任務做拓撲排序。dfs有兩個參數：graph代表圖，在這個問題中則代表需要排序的任務；而參數ordered是完成拓撲排序后返回的頂點鏈表。調用該函數會修改圖graph，因此如果有必要需要在調用前先對graph創建一個副本。另外，函數返回后鏈表ordered中保存了指向圖graph中頂點的指針，因此調用者必須保證，一旦訪問ordered中的元素就必須保證graph中的存儲空間保持有效。graph中的每一個頂點都是一個DfsVertex結構體，該結構體擁有兩個成員：data是指向頂點數據域部分的指針；而color在搜索過程中負責維護頂點的顏色信息。match函數是由調用者在初始化graph時通過參數傳遞給graph_init的，該函數應該只對DfsVertex結構體中的data成員進行比較。

dfs按照深度優先的方式進行搜索。dfs_main是實際執行搜索的函數。dfs中的最后一個循環保證對圖中所有未相連的元素完成了檢索。在dfs_main中逐個完成頂點的搜索并將其涂黑，然后插入鏈表ordered的頭部。最后，ordered就包含完整拓撲排序后的頂點。

dfs的時間復雜度是O（V+E），V代表圖中的頂點個數，而E代表邊的個數。這是因為初始化頂點的顏色信息需要O（V）的時間，而dfs_main的時間復雜度為O（V+E）。

示例3：深度優先搜索的頭文件

/*dfs.h*/
#ifndef DFS_H
#define DFS_H

#include "graph.h"
#include "list.h"

/*為深度優先搜索中的所有節點定義一個結構體*/
typedef struct DfsVertex_
{
    void *data;
    VertexColor color;
}DfsVertex;

/*公共接口*/
int dfs(Graph *graph,List *ordered);

#endif // DFS_H

 示例4：深度優先搜索的函數實現

/*dfs.c*/
#include <stdlib.h>

#include "dfs.h"
#include "graph.h"
#include "list.h"

/*dfs_main*/
static int dfs_main(Graph *graph, AdjList *adjlist, List *ordered)
{
    AdjList   *clr_adjlist;
    DfsVertex *clr_vertex, *adj_vertex;
    ListElmt  *member;
    
    /*首先，將起始頂點涂成灰色，并遍歷它的鄰接頂點集合*/
    ((DfsVertex *)adjlist->vertex)->color = gray;
    
    for(member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member))
    {
        /*決定下一個集合頂點的顏色*/
        adj_vertex = list_data(member);
        
        if(graph_adjlist(graph,adj_vertex,&clr_adjlist) != 0)
        {
            return -1;
        }
        
        clr_vertex = clr_adjlist->vertex;
        /*如果當前頂點是白色，則遞歸搜索它的鄰接點*/
        if(clr_vertex->color == white)
        {
            if(dfs_main(graph,clr_adjlist,ordered) != 0)
                return -1;
        }
    }
    
    /*把當前頂點涂成“黑”色，并加入到鏈表頭部*/
    ((DfsVertex *)adjlist->vertex)->color = black;
    
    if(list_ins_next(ordered, NULL, (DfsVertex *)adjlist->vertex) !=0 )
        return -1;
    
    return 0;
}

/*dfs*/
int dfs(Graph *graph, List *ordered)
{
    DfsVertex *vertex;
    ListElmt  *element;
    
    /*初始化圖中的所有頂點*/
    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        vertex = ((AdjList *)list_data(element))->vertex;
        vertex->color = white;
    }
    
    /*執行廣度優先搜索*/
    list_init(ordered,NULL);
    
    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        /*確保圖中的每個頂點都能被檢索到*/
        vertex = ((AdjList *)list_data(element))->vertex;
        
        if(vertex->color == white)
        {
            if(dfs_main(graph, (AdjList *)list_data(element), ordered) != 0)
            {
                list_destroy(ordered);
                return -1;
            }
        }
    }
    
    return 0;
}

以上就是bfs和dfs的應用實例分析，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。