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

 

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

写在最前的三点:

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、小测试:

时间: 2024-10-27 08:58:28

图论中DFS与BFS的区别、用法、详解?的相关文章

CSS中伪类及伪元素用法详解

原文:CSS中伪类及伪元素用法详解 伪类的分类及作用: 注:该表引自W3School教程 伪元素的分类及作用: 接下来让博主通过一些生动的实例(之前的作业或小作品)来说明几种常用伪类的用法和效果,其他的读者可以自己尝试:   :active  大致效果为用鼠标点击时,元素增加特效,鼠标松开时,特效消失.多用在按钮的点击上.  写法: 这里id为box的是一div块,在css中首先设置了他的基本样式,下面为加入:active伪类后需要修改的样式. 未点击时: 点击之后: :active.:hove

Java中volatile关键字的作用与用法详解_java

volatile这个关键字可能很多朋友都听说过,或许也都用过.在Java 5之前,它是一个备受争议的关键字,因为在程序中使用它往往会导致出人意料的结果.在Java 5之后,volatile关键字才得以重获生机. volatile 关键字作用是,使系统中所有线程对该关键字修饰的变量共享可见,可以禁止线程的工作内存对volatile修饰的变量进行缓存. volatile 2个使用场景: 1.可见性:Java提供了volatile关键字来保证可见性. 当一个共享变量被volatile修饰时,它会保证修

Android MotionEvent中getX()和getRawX()的区别实例详解

Android MotionEvent中getX()和getRawX()的区别实例详解 实例代码: public class Res extends Activity implements View.OnTouchListener { Button btn = null; int x = 0; int y = 0; int rawx = 0; int rawy = 0; @Override public void onCreate(Bundle savedInstanceState) { sup

C#中Property和Attribute的区别实例详解

  本文实例分析了C#中Property和Attribute的区别.分享给大家供大家参考.具体分析如下: 在C#中有两个属性,分别为Property和Attribute,两个的中文意思都有特性.属性之间,但是用法上却不一样,为了区别,本文暂把Property称为特性,把Attribute称为属性. Attribute才是本文的主角,把它称为属性我觉得很恰当.属性的意思就是附属于某种事物上的,用来说明这个事物的各种特征的一种描述.而Attribute就是干这事的.它允许你将信息与你定义的C#类型相

Android 中SP与DP的区别实例详解_Android

从一开始写Android程序,就被告知这些常识 1.长度宽度的数值要使用dp作为单位放入dimens.xml文件中 2.字体大小的数值要使用sp作为单位,也放入dimens.xml文件中 然后,就没有然后了,仿佛潜台词就是说,你记住去用就行了. 偶然有一天,当我们阴差阳错地将字体写成了dp,也是可以工作,而且效果和sp一样. 这时候,就开始怀疑了,到底有啥区别呢,dp和sp有什么不同呢? 我们做个简单的Sample验证一下,如下,一个布局代码 <TextView android:layout_w

Python中生成器和yield语句的用法详解_python

 在开始课程之前,我要求学生们填写一份调查表,这个调查表反映了它们对Python中一些概念的理解情况.一些话题("if/else控制流" 或者 "定义和使用函数")对于大多数学生是没有问题的.但是有一些话题,大多数学生只有很少,或者完全没有任何接触,尤其是"生成器和yield关键字".我猜这对大多数新手Python程序员也是如此. 有事实表明,在我花了大功夫后,有些人仍然不能理解生成器和yield关键字.我想让这个问题有所改善.在这篇文章中,我将

oracle中的exists 和not exists 用法详解(转)

有两个简单例子,以说明 "exists"和"in"的效率问题 1) select * from T1 where exists(select 1 from T2 where T1.a=T2.a) ;     T1数据量小而T2数据量非常大时,T1<<T2 时,1) 的查询效率高. 2) select * from T1 where T1.a in (select T2.a from T2) ;      T1数据量非常大而T2数据量小时,T1>&g

css中link和@import的区别分析详解

导入CSS文件主要有两种方式: 链接式(link)  代码如下 复制代码 <link rel="stylesheet" href="style.css" type="text/css"/>   导入式(@impot) <style type="text/css">      @import url("style.css"); </style> 以上是这两种方式的语法区别.

Android 中SP与DP的区别实例详解

从一开始写Android程序,就被告知这些常识 1.长度宽度的数值要使用dp作为单位放入dimens.xml文件中 2.字体大小的数值要使用sp作为单位,也放入dimens.xml文件中 然后,就没有然后了,仿佛潜台词就是说,你记住去用就行了. 偶然有一天,当我们阴差阳错地将字体写成了dp,也是可以工作,而且效果和sp一样. 这时候,就开始怀疑了,到底有啥区别呢,dp和sp有什么不同呢? 我们做个简单的Sample验证一下,如下,一个布局代码 <TextView android:layout_w