學習筆記：圖的DFS和BFS的兩種搜尋辦法

在學習圖結構的過程中，DFS和BFS是兩種不同的周遊方式，其尋找元素具有不同的優點和缺陷。

BFS被稱作廣度優先算法， 在周遊整個圖的過程中，BFS将采用入隊的方式進行，值得一提的是，這和樹結構中的層序周遊有很大的相似之處。

在層序周遊中，将父親節點入隊後，在父親節點出隊後，将其兒子節點入隊。

同理在圖的BFS周遊中，先讓BFS的首元素入隊，在收元素入隊後将他的兒子節點入隊，放能夠實作BFS搜尋，他們的整體思想是一樣的。

1 void TraversalGraph_BFS(LGraph Graph,Vertex vertex){
 2     Visit(vertex);
 3     VISIT[vertex]=1;
 4     enqueue(queue,vertex);
 5     while(!isEmpty(queue)){
 6         DelQueue(queue);
 7         for(w=Graph->G[vertex].FirstNode;w;w=w->Next){
 8             if(!Visit[w]){
 9                 Visit[w];
10                 Visit[w->vertex]=1;
11                 enqueue(queue,w);
12             }
13         }
14     }
15 }      

DFS又被稱作深度優先算法，與BFS不同的是，DFS會首先周遊其兒子節點，這樣有點類似在樹結構中的前序周遊。

在了解方面相比比較容易，DFS采用了遞歸的思路，在用連結清單實作DFS時，思路是當遇到一個沒有周遊的節點，則進入該節點，然後同理往下遞歸，直到某個節點無法在繼續則傳回。

1 void TraversalGraph_DFS(LGraph Graph,Vertex vertex,void(*Visit)(Vertex)){
2     PtrToAdjVNode W;
3     Visit(vertex);
4     Visit[vertex]=1;
5     for(w=Graph->G[vertex].FirstNode;w;w=w->Next){
6         if(!Visit[w->vertex])
7             TraversalGraph_DFS(Graph,w->Vertex)
8     }
9 }      

下面是程式結構體的前置定義

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct Enode *PtrToEnode;
 5 typedef int Vertex;
 6 typedef int WeightType;
 7 typedef DataType Data;
 8 struct Enode{
 9     Vertex v1,v2;
10     WeightType Weight;
11 };
12 typedef PtrToEnode Edge;
13 
14 typedef struct AdjVNode *PtrToAdjVNode;
15 struct AdjVNode{
16     Vertex vertex;
17     WeightType Weight;
18     PtrToAdjVNode Next;
19 };
20 
21 typedef struct HeadNode *PtrToHead;
22 struct HeadNode{
23     PtrToAdjVNode FirstNode;
24     DataType Data;
25 }HeadNode[Max];
26 
27 typedef struct Graph *PtrToGNode;
28 struct Graph{
29     int Ne;
30     int Nv;
31     HeadNode G;
32 };
33 typedef *PtrToGNode LGraph;
34 
35 LGraph creatGraph(int MaxNumb){
36     LGraph Graph;
37     Graph=(LGraph)malloc(sizeof(struct Graph));
38     Graph->Ne=0;
39     Graph->Nv=MaxNumb;
40     for(i=0;i<Graph->Nv;i++){
41         Graph->G[i].FirstNode=NULL;
42     }
43     return(Graph);
44 }
45 
46 void Insert(LGraph Graph,Edge E){
47     AdjVNode NewNode;
48     NewNode=(PtrToAdjVNode)malloc(sizeof(struct AdjVNode))
49     NewNode->Weight=E->W;
50     NewNode->vertex=E->v1
51     Graph->G[E->v2].Next=NewNode->Next;
52     Graph->G[E->v2].Next=NewNode;
53 }
54 
55 void Visit(LGraph Graph){
56     printf("Now VISIT %d",V);
57 }      

轉載于:https://www.cnblogs.com/hakase/p/5904395.html