图论中DFS与BFS的区别、用法、详解?

时间:2023-04-14 20:16:38

写在最前的三点:

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

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

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

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

图论中DFS与BFS的区别、用法、详解?

一、深度优先搜索遍历

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

① 访问v

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

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

在于递归使得初学者难以把握程序运行到何处了!一点建议就是先学好递归,把握函数调用是的种种。

3、算法代码:

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

4、小测试

图论中DFS与BFS的区别、用法、详解?

二、广度优先搜索遍历

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

①访问v

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

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

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

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

3、算法代码:

[cpp] view plain copy    
  1. #include
  2. #include
  3. using namespace std;
  4. int a[11][11];
  5. bool visited[11];
  6. void store_graph()
  7. {
  8. for(int i=1;i<=10;i++)
  9. for(int j=1;j<=10;j++)
  10. cin>>a[i][j];
  11. }
  12. void bfs_graph()
  13. {
  14. void bfs(int v);
  15. memset(visited,false,sizeof(visited));
  16. for(int i=1;i<=10;i++)
  17. if(visited[i]==false)
  18. bfs(i);
  19. }
  20. void bfs(int v)
  21. {
  22. int Adj(int x);
  23. queue<<span
    class="datatypes" style="margin: 0px; padding: 0px; border: none;
    color: rgb(46, 139, 87); background-color: inherit; font-weight:
    bold;">int> myqueue;
  24. int adj,temp;
  25. cout<<v<<" ";
  26. visited[v]=true;
  27. myqueue.push(v);
  28. while(!myqueue.empty())    //队列非空表示还有顶点未遍历到
  29. {
  30. temp=myqueue.front();  //获得队列头元素
  31. myqueue.pop();         //头元素出对
  32. adj=Adj(temp);
  33. while(adj!=0)
  34. {
  35. if(visited[adj]==false)
  36. {
  37. cout<<adj<<" ";
  38. visited[adj]=true;
  39. myqueue.push(adj);   //进对
  40. }
  41. adj=Adj(temp);
  42. }
  43. }
  44. }
  45. int Adj(int x)
  46. {
  47. for(int i=1;i<=10;i++)
  48. if(a[x][i]==1 && visited[i]==false)
  49. return i;
  50. return 0;
  51. }
  52. int main()
  53. {
  54. cout<<"初始化图:"<<endl;
  55. store_graph();
  56. cout<<"bfs遍历结果:"<<endl;
  57. bfs_graph();
  58. return 0;
  59. }

4、小测试:

图论中DFS与BFS的区别、用法、详解?