【经典算法】:BFS与DFS

超、凢脫俗 2022-08-23 04:52 181阅读 0赞

写在最前的三点：

1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。

2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法：邻接矩阵和邻接表。这里为简单起

见，均采用邻接矩阵存储，说白了也就是二维数组。

3、本文章的小测试部分的测试实例是下图：

![1335771553_1623.PNG][]

一、深度优先搜索遍历

1、从顶点v出发深度遍历图G的[算法][Link 1]

① 访问v

② 依次从顶点v未被访问的邻接点出发深度遍历。

2、一点心得：dfs算法最大特色就在于其递归特性，使得算法代码简洁。但也由于递归使得算法难以理解，原因

在于递归使得初学者难以把握程序运行到何处了！一点建议就是先学好递。

3、算法代码：

**\[cpp\]** [ view plain][view plain] [ copy][view plain] [ print][view plain][?][view plain]

1.  \#include<iostream>  
2.  using namespace std;  
3.    
4.  int a\[11\]\[11\];  
5.  bool visited\[11\];  
6.    
7.  void store\_graph()  //邻接矩阵存储图  
8.  \{  
9.      int i,j;  
10.   
11.     for(i=1;i<=10;i++)  
12.         for(j=1;j<=10;j++)  
13.             cin>>a\[i\]\[j\];  
14. \}  
15.   
16. void dfs\_graph()    //深度遍历图  
17. \{  
18.     void dfs(int v);  
19.   
20.     memset(visited,false,sizeof(visited));  
21.   
22.     for(int i=1;i<=10;i++)  //遍历每个顶点是为了防止图不连通时无法访问每个顶点  
23.         if(visited\[i\]==false)  
24.             dfs(i);  
25. \}  
26.   
27. void dfs(int v)  //深度遍历顶点  
28. \{  
29.     int Adj(int x);  
30.   
31.     cout<<v<<" ";  //访问顶点v  
32.     visited\[v\]=true;  
33.   
34.     int adj=Adj(v);  
35.     while(adj!=0)  
36.     \{  
37.         if(visited\[adj\]==false)     
38.             dfs(adj);      //递归调用是实现深度遍历的关键所在  
39.   
40.         adj=Adj(v);  
41.     \}  
42. \}  
43.   
44. int Adj(int x)   //求邻接点  
45. \{  
46.     for(int i=1;i<=10;i++)  
47.         if(a\[x\]\[i\]==1 && visited\[i\]==false)  
48.             return i;  
49.   
50.     return 0;  
51. \}  
52.   
53. int main()  
54. \{  
55.     cout<<"初始化图:"<<endl;  
56.     store\_graph();  
57.   
58.     cout<<"dfs遍历结果:"<<endl;  
59.     dfs\_graph();  
60.   
61.     return 0;  
62. \}

4、小测试

![1335770710_6217.PNG][]

二、广度优先搜索遍历

1、从顶点v出发遍历图G的算法买描述如下：

①访问v

②假设最近一层的访问顶点依次为vi1,vi2,vi3...vik，则依次访问vi1,vi2,vi3...vik的未被访问的邻接点

③重复②知道没有未被访问的邻接点为止

2、一点心得：bfs算法其实就是一种层次遍历算法。从算法描述可以看到该算法要用到队列这一[数据结构][Link 1]。我这

里用STL中的<queue>实现。该算法由于不是递归算法，所以程序流程是清晰的。

3、算法代码：

**\[cpp\]** [ view plain][view plain] [ copy][view plain] [ print][view plain][?][view plain]

1.  \#include<iostream>  
2.  \#include<queue>      
3.  using namespace std;  
4.    
5.  int a\[11\]\[11\];  
6.  bool visited\[11\];  
7.    
8.  void store\_graph()    
9.  \{  
10.     for(int i=1;i<=10;i++)  
11.         for(int j=1;j<=10;j++)  
12.             cin>>a\[i\]\[j\];  
13. \}  
14.   
15. void bfs\_graph()      
16. \{  
17.     void bfs(int v);  
18.   
19.     memset(visited,false,sizeof(visited));  
20.   
21.     for(int i=1;i<=10;i++)    
22.         if(visited\[i\]==false)  
23.             bfs(i);  
24. \}  
25.   
26. void bfs(int v)  
27. \{  
28.     int Adj(int x);  
29.   
30.     queue<int> myqueue;  
31.     int adj,temp;  
32.   
33.     cout<<v<<" ";  
34.     visited\[v\]=true;  
35.     myqueue.push(v);  
36.   
37.     while(!myqueue.empty())    //队列非空表示还有顶点未遍历到  
38.     \{  
39.         temp=myqueue.front();  //获得队列头元素  
40.         myqueue.pop();         //头元素出对  
41.   
42.         adj=Adj(temp);  
43.         while(adj!=0)  
44.         \{  
45.             if(visited\[adj\]==false)  
46.             \{  
47.                 cout<<adj<<" ";  
48.                 visited\[adj\]=true;  
49.                 myqueue.push(adj);   //进对  
50.             \}  
51.   
52.             adj=Adj(temp);  
53.         \}  
54.     \}  
55. \}  
56.   
57. int Adj(int x)     
58. \{  
59.     for(int i=1;i<=10;i++)  
60.         if(a\[x\]\[i\]==1 && visited\[i\]==false)  
61.             return i;  
62.   
63.     return 0;  
64. \}  
65.   
66. int main()  
67. \{  
68.     cout<<"初始化图:"<<endl;  
69.     store\_graph();  
70.   
71.     cout<<"bfs遍历结果:"<<endl;  
72.     bfs\_graph();  
73.   
74.     return 0;  
75. \}

[1335771553_1623.PNG]: https://img-my.csdn.net/uploads/201204/30/1335771553_1623.PNG
[Link 1]: http://lib.csdn.net/base/datastructure
[view plain]: http://blog.csdn.net/lulipeng_cpp/article/details/7524133#
[1335770710_6217.PNG]: https://img-my.csdn.net/uploads/201204/30/1335770710_6217.PNG