共計 6204 個字符，預計需要花費 16 分鐘才能閱讀完成。
本篇文章給大家分享的是有關 bfs 和 dfs 的應用實例分析，丸趣 TV 小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著丸趣 TV 小編一起來看看吧。
廣度優先搜索應用舉例：計算網絡跳數
圖結構在解決許多網絡相關的問題時直到了重要的作用。
比如，用來確定在互聯網中從一個結點到另一個結點（一個網絡到其他網絡的網關）的最佳路徑。一種建模方法是采用無向圖，其中頂點表示網絡結點，邊代表結點之間的聯接。使用這種模型，可以采用廣度優先搜索來幫助確定結點間的最小跳數。
如圖 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 的應用實例分析，丸趣 TV 小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注丸趣 TV 行業資訊頻道。
