精华内容
下载资源
问答
  • 转自:https://blog.csdn.net/github_38818603/article/details/81288659
    展开全文
  • 浅析DFSBFS的异同,图的和深度优先遍历和广度优先遍历有什么不同,DFSBFS有什么区别?时间复杂度是多少? 一、深度优先遍历DFS) 1.定义 图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:...


    浅析DFS与BFS的异同,图的和深度优先遍历和广度优先遍历有什么不同,DFS与BFS有什么区别?时间复杂度是多少?

    一、深度优先遍历(DFS)

    1.定义

    图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v,
    并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点w,并访问它:再选取与w邻接
    的未被访问的任一项点并访问,以此重复进行。当一个顶点所有的邻接顶点都被访问过时,则依次退回到最近被访问过的顶点,若该顶点还有其他邻接顶点未被访问,则从这些未被访问的顶点中取一一个并重复上述访问过程,直至图中所有顶点都被访问过为止。图7-8所示即为一个图的深度优先搜索遍历过程。

    在这里插入图片描述

    图及定义摘自天勤,天勤no.1.

    二、广度优先遍历(BFS)

    1.定义

    图的广度优先搜索遍历(BFS) 类似于树的层次遍历。它的基本思想是:首先访问起始顶点V,然
    后选取与v邻接的全部顶点w,… w。进行访问,再依次访问与WI,… w。邻接的全部顶点(已经
    访问过的除外),以此类推,直到所有顶点都被访问过为止。
    广度优先搜索遍历图的时候,需要用到一一个队列(二叉树的层次遍历也要用到队列),算法执行过程
    可简单概括如下:
    1)任取图中一个顶点访问,入队,并将这个顶点标记为已访问;
    2)当队列不空时循环执行:出队,依次检查出队顶点的所有邻接顶点,访问没有被访问过的邻接顶
    点并将其入队;
    3)当队列为空时跳出循环,广度优先搜索即完成。

    三、异同

    1.相同点

    时间复杂度是相同的!
    时间复杂度是相同的!
    时间复杂度是相同的!
    书上没有明确指明这一点,但是严奶奶的数据结构写到:
    在这里插入图片描述
    图源https://www.cnblogs.com/hi3254014978/p/12627861.html

    2.不同点

    (1)DFS

    1. 提供回溯,可以更新,完成并查集等算法
    2. 适用于有条件约束的问题,如棋盘问题
    3. 可以判断是否连通

    (2)BFS

    1. 求最短路径
    2. 迷宫问题等

    先挖个坑,有机会再逐渐补充完善。

    展开全文
  • 二刷数据结构,总结归纳一下树/图的遍历区别 以前一直分不清,学的稀里糊涂的…这次系统的认真看了数据结构,实现了代码,总结了几点纳一下树/图的遍历。(使用的是王道408复习教材) 建议看一下我上一篇博客,实现...

    二刷数据结构,总结归纳一下树/图的遍历区别

    以前一直分不清,学的稀里糊涂的…这次系统的认真看了数据结构,实现了代码,总结了几点纳一下树/图的遍历。(使用的是王道408复习教材)

    建议看一下我上一篇博客,实现的Dijkstra,收益匪浅,用时1h40m(编码小白很是欣慰==)


    好了,接下来总结一下:

    • 首先,图没有根结点,不像树的遍历,可以从root开始,图的遍历一般要指定开始的结点,而且图的任意顶点都可能和其余顶点相连接,所以为避免重复访问,设置bool visited[]数组记录结点是否被访问,同时,我设置了int num去统计已经访问了的结点个数,自然而然,while()的判断条件就是while(num!=n)BFS和DFS的遍历结果并不唯一

    • BFS我大概9分钟把完整的代码写完了,需要注意的是每次要判断
      !visited[i] 这个值,题主每次判断qu.empty()时老是忘记加 !,不要学我

    • DFS第一次实现结果错了,因为 题主用邻接矩阵存储图,人为地输入 左小结点右大结点这样真的很不严谨…其实啊,无向图的邻接矩阵本来就就有冗余…而我只存了一半…导致我在入栈的时候,可能找不到相邻结点了

      输入数据时为:
      5 6 1
      1 2
      1 5
      2 3
      2 4
      3 4
      4 5
      然后1出栈,2,5入栈,5为栈顶,但是此时在邻接矩阵中5是没有相邻顶点的,所以直接出栈了,然后2位栈顶,很明显不对。然后我改了一下存储图的代码

    int temp1,temp2;
    	cin>>N>>M>>start;
    	for(int i=1;i<=M;i++){ 
    	cin>>temp1>>temp2;
    	ljjz[temp1][temp2]=1;
    	
    	}
    

    代码区:

    /*
    图的BFS与DFS算法
    20:06 
    20:17
    */
    #include<bits/stdc++.h>
    #define INF 999
    using namespace std;
    //采用邻接矩阵存储 
    int ljjz[100][100];
    
    void DFS(int N,int M,int s){
    	vector<int>res;
    	bool visited[100];
    	int num_of_true=0;
    	for(int i=1;i<=N;i++){
    		visited[i]=false;
    	}
    	stack<int>st;
    	st.push(s);
    	while(num_of_true!=N){
    		int now=st.top();
    		visited[now]=true;
    		++num_of_true;
    		res.push_back(now);
    		st.pop();
    		for(int i=1;i<=N;i++){
    			if(ljjz[now][i]&&!visited[i]){
    				st.push(i);
    			}
    		}
    	}
    	for(int i=0;i<res.size();i++)
    		cout<<res[i]<<" ";
    	
    	
    }
    
    void BFS(int N,int M,int s){
    	vector<int>res;
    	bool visited[100];
    	int num_of_true=0;
    	for(int i=1;i<=N;i++){
    		visited[i]=false;
    	}
    	queue<int>qu;
    	qu.push(s);
    	while(num_of_true!=N){
    		int now=qu.front();
    		visited[now]=true;
    		++num_of_true;
    		res.push_back(now);
    		qu.pop();
    		for(int i=1;i<=N;i++){
    			if(ljjz[now][i]&&!visited[i]){
    				qu.push(i);
    			}
    		}
    	}
    	for(int i=0;i<res.size();i++)
    		cout<<res[i]<<" ";
    	
    } 
    
    int main(){
    	int N,M,start;
    	int temp1,temp2;
    	cin>>N>>M>>start;
    	for(int i=1;i<=M;i++){ 
    	cin>>temp1>>temp2;
    	ljjz[temp1][temp2]=1;
    	ljjz[temp2][temp1]=1;
    	}
    //	BFS(N,M,start);
    	DFS(N,M,start);
    	return 0;
    } 
    
    展开全文
  • DFSBFS的区别、用法、详解? 写在最前的三点: 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。 2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接矩阵邻接表...

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

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

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

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

     

    一、深度优先搜索遍历

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

    ① 访问v

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

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

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

    3、算法代码:

    [cpp] view plain copy   
    1. #include  
    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、小测试

     

    二、广度优先搜索遍历

    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.   
    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<<span class="datatypes" style="margin: 0px; padding: 0px; border: none; color: rgb(46, 139, 87); background-color: inherit; font-weight: bold;">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. }  

    4、小测试:

    展开全文
  • 通过DFS和BFS判断无向是否连通

    万次阅读 2017-11-27 22:18:30
    连通图:任意两个顶点可以直接或者通过其他顶点走通,那么就是连通图,和完全图需要区别(完全图是需要任意两个顶点直接有路)遍历图的基本方法来判断是否连通DFS和BFS有的步骤都是从一个顶点开始,然后判断该顶点...
  • 图论dfs和bfs的感想

    2016-10-27 17:51:16
    对于最开始的图的基本遍历dfs和bfs的顺序不一样,但是遍历的终止条件都是一样的,那就是if(sum==n) return;当作题的时候有得是无向图有得是有向图,他们的区别就是在初始化地图的时候,在初始化map[a][b]=?后用不用...
  • DFSBFS的区别、用法、详解? 写在最前的三点: 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。 2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接...
  • DFS和BFS详解

    千次阅读 2018-09-09 13:47:28
    BFSDFS区别,详解 写在最前的三点:  1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。  2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接矩阵邻接表。这里为简单...
  • DFSBFS的区别、用法、详解?

    千次阅读 2016-11-25 15:52:35
    2、实现bfs和dfs都需要解决一个问题就是如何存储。一般有两种方法:邻接矩阵邻接表。这里为简单起 见,均采用邻接矩阵存储,说白了也就是二维数组。 3、本文章小测试部分测试实例是下: ...
  • DFS和BFS算法介绍

    千次阅读 2016-11-03 16:55:20
    这篇文章合适对深度优先遍历和广度优先遍历原理有一定了解的同志阅读,深度广度这两个概念大家都知道的:通过邻接表存储,深度就是有多少层,广度就是有多宽,两者原理上的区别DFS优先纵向访问,BFS优先横向...
  • BFS和DFS直观区别 FLY

    2019-08-19 16:18:52
    我们首次接触 BFS DFS 时,应该是在数据结构课上讲的 “图的遍历”。还有就是刷题的时候,遍历二叉树我们会经常用到BFS和DFS。它们的实现都很简单,这里我就不哆嗦去贴代码了。 想看代码的可以看《剑指Offer(三...
  • BFSDFS区别,详解

    万次阅读 多人点赞 2017-08-18 21:14:36
    BFSDFS区别,详解写在最前的三点: 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。 2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接矩阵邻接表。这里为简单起 ...
  • 6-14 实验2-BFS和DFS应用 ... 2.BFS相当于图版层次遍历区别只在于每次入队节点数可能会大于2,与DFS和前序遍历的关系相似。换句话说,BFS和DFS是泛化层次遍历和前序遍历BFS和DFS在所给的图为二叉树时.
  • 2、实现bfs和dfs都需要解决一个问题就是如何存储。一般有两种方法:邻接矩阵邻接表。这里为简单起 见,均采用邻接矩阵存储,说白了也就是二维数组。 3、本文章小测试部分测试实例是下: 一、深度优先...
  • DFSBFS对比

    2017-06-03 16:50:00
    深度优先遍历图算法步骤: 1.访问顶点v 2,。依次从v未被访问过邻接顶点出发,对图进行搜索(深度优先搜索)直至图中的和v相通顶点都被访问过; 3.若此时图中尚有顶点未被访问过,则从一个未访问顶点出发,...
  • BFS和DFS

    2019-08-29 10:20:05
    我们首次接触 BFS DFS 时,应该是在数据结构课上讲的 “图的遍历”。还有就是刷题的时候,遍历二叉树我们会经常用到BFS和DFS。 二、区别 广度优先搜索算法(Breadth-First-Search,缩写为 BFS),是一种利用...
  • Python算法之图的遍历

    2020-12-25 02:11:22
    本节主要介绍图的遍历算法BFS和DFS,以及寻找图的(强)连通分量的算法 Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点。对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit)。...
  • BFS相对DFS最主要的区别是:BFS找的的路径一定是最短的,代价是空间复杂度比DFS大很多。 再说一个重点,什么样的问题需要用到BFS? 这样的问题本质就是在抽象出来的上,找到起点start到终点target的最短路径,听...
  • 一、深度优先搜索DFS和广度优先BFS的 区别BFS是队列思想。 DFS是栈思想。 BFS思想: BFS是队列思想。如下BFS从起点A,把A附近点(B、C)先遍历遍历完(B、C)入队,然后再以B为起点,遍历B点附近...
  • 深度优先搜索(DFS)

    千次阅读 2020-02-13 23:00:44
    BFS 类似,深度优先搜索(DFS)是用于在树/遍历/搜索的另一种重要算法。也可以在更抽象的场景中...这也是 DFS BFS 之间最大的区别BFS永远不会深入探索,除非它已经在当前层级访问了所有结点。 模版 递归...
  • bfs和dfs(个人笔记)

    2021-02-10 17:15:14
    深度优先搜索广度优先搜索都是用来遍历一个图的,两种遍历方法的主要特点是 深度优先:不撞南墙不回头 广度优先:向外扩散 现在可能听起来很让人疑惑,接下来我们逐个来析: 深度优先搜索 深度优先搜索(Depth ...
  • 深度优先遍历(DFS) —— 栈堆 广度优先遍历(BFS) —— 队列 遍历目标: 寻找中某一节点到另一节点最短路径。 区别 栈堆:直接保存了遍历的最短路径 即,找到目标节点后栈堆内依旧存在节点就是其最短路径。...

空空如也

空空如也

1 2 3
收藏数 53
精华内容 21
关键字:

dfs和bfs遍历图的区别