BFS 、DFS区别，详解

迈不过友情╰ 2022-06-10 12:25 91阅读 0赞

## BFS 、DFS区别，详解 ##

写在最前的三点：  
1、所谓图的遍历就是按照某种次序访问图的每一顶点一次且仅一次。  
2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法：邻接矩阵和邻接表。这里为简单起见，均采用邻接矩阵存储，说白了也就是二维数组。  
3、本文章的小测试部分的测试实例是下图，图G。  
4、代码里store\_graph部分没有实现该图，按编号自己输进去吧。  
![图G][G]  
一、深度优先搜索遍历  
1、从顶点v出发深度遍历图G的算法  
① 访问v  
② 依次从顶点v未被访问的邻接点出发深度遍历。  
2、一点心得：dfs算法最大特色就在于其递归特性，使得算法代码简洁。但也由于递归使得算法难以理解，原因  
在于递归使得初学者难以把握程序运行到何处了！一点建议就是先学好递归，把握函数调用是的种种。  
3、算法代码：

#include<iostream>
    #include<string.h>
    using namespace std;  
    int a[11][11];  
    bool visited[11];  
      
    void store_graph()  //邻接矩阵存储图  
    {
          
        int i,j;  
      
        for(i=1;i<=10;i++)  
            for(j=1;j<=10;j++)  
                cin>>a[i][j];  
    }
    
    void dfs_graph()    //深度遍历图  
    {
          
        void dfs(int v);  
      
        memset(visited,false,sizeof(visited));  
      
        for(int i=1;i<=10;i++)  //遍历每个顶点是为了防止图不连通时无法访问每个顶点  
            if(visited[i]==false)  
                dfs(i);
    }
    
    void dfs(int v)  //深度遍历顶点  
    {
          
        int Adj(int x);  
      
        cout<<v<<" ";  //访问顶点v
        visited[v]=true;
      
        int adj=Adj(v);
        while(adj!=0)
        {
          
            if(visited[adj]==false)
                dfs(adj);      //递归调用是实现深度遍历的关键所在  
      
            adj=Adj(v);
        }  
    }
      
    int Adj(int x)   //求邻接点  
    {
        
        for(int i=1;i<=10;i++)  
            if(a[x][i]==1 && visited[i]==false)  
                return i;  
      
        return 0;  
    }
      
    int main()  
    {
          
        cout<<"初始化图:"<<endl;  
        store_graph();  
      
        cout<<"dfs遍历结果:"<<endl;  
        dfs_graph();  
      
        return 0;  
    }

4、小测试  
![这里写图片描述][d77edf8df8983f7a6f342e953eb09220.png]  
二、广度优先搜索遍历  
1、从顶点v出发遍历图G的算法买描述如下：  
①访问v  
②假设最近一层的访问顶点依次为vi1,vi2,vi3…vik，则依次访问vi1,vi2,vi3…vik的未被访问的邻接点  
③重复②知道没有未被访问的邻接点为止  
2、一点心得：bfs算法其实就是一种层次遍历算法。从算法描述可以看到该算法要用到队列这一数据结构。我这  
里用STL中的实现。该算法由于不是递归算法，所以程序流程是清晰的。  
3、算法代码：

#include<iostream>  
    #include<queue>
    #include<string.h>
    using namespace std;  
      
    int a[11][11];  
    bool visited[11];  
      
    void store_graph()    
    {
          
        for(int i=1;i<=10;i++)  
            for(int j=1;j<=10;j++)  
                cin>>a[i][j];  
    }  
      
    void bfs_graph()      
    {
          
        void bfs(int v);  
      
        memset(visited,false,sizeof(visited));  
      
        for(int i=1;i<=10;i++)    
            if(visited[i]==false)  
                bfs(i);  
    }  
      
    void bfs(int v)  
    {
          
        int Adj(int x);  
      
        queue<int> myqueue;  
        int adj,temp;  
      
        cout<<v<<" ";  
        visited[v]=true;  
        myqueue.push(v);  
      
        while(!myqueue.empty())    //队列非空表示还有顶点未遍历到  
        {
          
            temp=myqueue.front();  //获得队列头元素
            myqueue.pop();         //头元素出队
      
            adj=Adj(temp);  
            while(adj!=0)  
            {
          
                if(visited[adj]==false)  
                {
          
                    cout<<adj<<" ";  
                    visited[adj]=true;  
                    myqueue.push(adj);   //进队
                }  
      
                adj=Adj(temp);  
            }  
        }  
    }  
      
    int Adj(int x)     
    {
          
        for(int i=1;i<=10;i++)  
            if(a[x][i]==1 && visited[i]==false)  
                return i;  
      
        return 0;  
    }  
      
    int main()  
    {
          
        cout<<"初始化图:"<<endl;  
        store_graph();  
      
        cout<<"bfs遍历结果:"<<endl;  
        bfs_graph();  
      
        return 0;  
    }

4、小测试：  
![这里写图片描述][f9d66a12146176d25653f38ed161ba32.png]

[G]: /images/20220610/26e2140071144d1abf05f9b6846edb09.png
[d77edf8df8983f7a6f342e953eb09220.png]: /images/20220610/538333958f124cee94ba2a70baa844fa.png
[f9d66a12146176d25653f38ed161ba32.png]: /images/20220610/c9c852b5050b41848bfa01fcec885034.png