00:00
同学们,我们来举一个例子来比较一下这个广度优先和深度优先的它的一个区别,因为前面我们举的这个例子呢,它广度优先和深度优先结果都一样,看不出来区别,所以说我们再看一个案例,同学们看这有个案例,那这个案例呢,它的节点就相对比较多一点,一共有。八个节点,那八个节点它的一个图呢,是这样一个图。好,那我们先来看,如果我们不用程序运行,它的深度优先的顺序应该是什么呢?深度优先就应该是先便利12485对不对,到这就没有了,然后呢,一这边继续往下编离一就这边就是三了,就是六就是七,因此它的顺序是12485365。367,那如果说同学们,如果我们现在是广度优先,大家知道广度优先它是一层一层的便利,所以说它先把第一层遍历了,那就是一遍利完毕再遍历二第二层,那就是123,然后第三层4567,第四层八,也就这个广度优先,它的结果应该是12345678。
01:13
OK,那现在呢,我们来给大家测一下。好的,首先呢,我我把这个各位朋友把这个顶点呢,给大家做一个。变化,我们把这个顶点变成一二。三。是。五对不对,这个就应该是六这个是。七这个是八没有问题吧,好,紧接着我们把它的这个边,以前这个边的关系呢,先拿掉我们更新一下,就说我们更新。边的边的一个关系好,那边一共有几条边,大家数一下,一共有。九条边123456789好,那么它们边的关系呢,我这已经给大家写好了,你看啊,0101就代表。
02:05
这这个一,第一个节点和第二个节点的关系,对吧,零二就代表第一个节点和第三个节点的关系,那我这就偷个懒了,因为我这已经准备好了,我就粘过来九条边的关系就有了,好的九条边的关系有了,过后我们先来看一下它的图,长得跟我们想想象的一样还是不一样瘦。我们运行,当我们运行的时候呢,我们发现这里抛出了一个数组越界为,为什么呀,同学们是不是因为这个问题啊,因为你呢,这个地方节点你设置成四五,是不是应该把它改成八呀。是这样子的吧,我们在运行,当我们再次运行的时候呢,我们可以看到,诶这个情况跟我们想的就一样了是吧?好这个我就不去看了啊好,紧接着呢,我们打开打开它的这一个深度便利,看看深度便利跟我们想的一样否?那么我们来检查一下深度便利代码有没有问题,先看一下各位同学看这就有问题了,因为现在我们的节点的个数不再是五个了,应该是多少个呀,应该是八个,所以说你这为了做做的做的比较灵活一点呢,你可以把这个赛字给它填进去就行了,好同样道理,我们进行这一个广度优先的时候呢,我们仍然会把这段这个五呢,也把它改成它实际的一个大小是这样子的,同学们。
03:26
诶改一下这个没不费事儿。Vertex。Vertex list size,这样就比较灵活了,好,同学们现在呢?我们先运行一下这个所谓的深度优先,深度优先根据刚才我们。这个进行分析的结果,它的顺序应该是这样子的,是不是深度优先,它尽量向纵向,纵向去进行便利,好我们运行一把,看看结果对不对。好,各位同学请看是比较一下12485367,完全的正确,完全正确,好的,现在呢,我们再打开广度优先各位广度优先我们刚才也做了一个分析,应该是顺序的一呃,我把这个粘过来吧,省点事啊,那就是。
04:17
按照12345678的顺序来进行一个遍历的,是不是按照同学们我们运行把吧运行。好,我们看这个结果,诶12345678正确,所以说同学们经过这个案例就能够看到广度优先和深度优先,其实它还是有区别的,区别还很大,对不对,不是说诶好像说一模一样,因为我前面举的例子呢,这个节点它太少了,就看起来好像都是abcde是吧,其实是算法不一样的,好同学们,那么关于我们图的这一部分基础的内容呢,就给大家讲完了,其实我们讲的就是图的创建。然后呢,然后呢,怎么去用,用一个临界矩阵表示,然后讲了深度优先和广度优先,那我们把这块讲的内容给大家做一个板书,我们来看看我们这块讲了哪些内容对不对。
05:09
图的表示方式这块已经做了板书了。我们看板书已经到哪里了?诶,OK,到这儿了,我们接着往下看。那么我们把图的基本的概念介绍清楚,过后呢,我们先给同学们讲的是图的一个快速入门。说白了就是让大家能够快速的创建一个图,用矩阵来表示的图,OK,那这边是我们的要求。是吧,我们做要求要求干什么呢。就是让大家第一步根据。一个给出的图形,这个图形就这样子的,根据这个给出这个图形呢,把它的这一个矩阵给搞定,是这样子吧,诶就这样子的一个概念,我们捋一捋,思路也很重要啊,把这个要求说完了以后呢,我们就说我们先给大家做了思路分析,就说是怎么怎么一步步做。
06:06
呃,做过来的,我们先做了一个思路分析。这是第二步。这是我们的第二步。对,第三步呢,我们就用代码给各位朋友实现了一码,那我先把代码,那这个代码就没法没没法截取了,为什么呢?因为我整个graph其实都是写在这一起的,那这个截取就比较困难了,对吧,因为这一个月的截太累了,那我可以把核心的代码先放过来。这还不好,不好放。啊,不好放。因为核心的代码,这个创建图的核心代码,其实同学们,呃,就是这一个是insert的vertex,一个是insert edge,其实这两个是它核心代码。对不对,核心代码先放这吧,那么后面呢,再来一个汇总不就完了吗?啊,这是它的核心代码,我再写个汇总代码,后面汇总代码在后边,好吧,也写到这,那大致知道是怎么来的,当我们把这个图的创建搞定以后呢,我们紧接着就给大家介绍了图的深度优先便利的这么一个。
07:15
呃,算法是怎么回事?那怎么介绍这个的呢?首先我们说图的遍历有两种策略,一种是深度,一种是广度,对吧?然后呢,我们又讲了深度优先的基本思想。好的,同学们,我们板书到这里。对。我们说他的基本思想是在这个位置给他讲的,大概呢,分成这么几步。啊,分成这么几步。下面这两步吧,捋一捋。对吧,选择这个地方啊,是分三步来讲的。那图的深度优先呢,它叫deep first search,那有些人呢,就直接叫DFSDF。呃,DFS就简写的好,那把这个基本事项说完了以后,是不是我们就给大家介绍了一个深度优先遍历算法的具体步骤,我把这个步骤也给同学们罗列到这里。
08:11
对吧,但是这个步骤如果仅仅用文字来描述,同学们很难理解,所以说呢,我们就给大家举了一个实际的案例,用这个案例大家分析了一把。是不是啊,但是很遗憾这个地方我没有把分析的那个啊分析分析图,分析的那个图呢,我是在用用这个画笔画的,没有保留下来哈,很遗憾,那放这吧,你应该也不是很难。那想不起来就去看一下视频就可以了。好的,那这个讲完了过后,是不是我们就直接给大家用深度优先给他写,写了一段程序啊啊写了一段代码,好,我直接把代码拿过来。这是就是叫做深度优先。写到这啊,深度优先算法,算法的代码实现。
09:03
是这样子吧,同学们。那深度优先代码实现它的核心代码是哪一块呢?其实就是两个方法,还记得吧,就是两个方法,我把这两个方法呢,核心的方法给大家拿过来。一个就是这。是吧,还有下面这个负循环。这是它的核心代码,我们放到这吧。大家呢,如果只看部分就可以看到这这是核心代码。OK,放到这里好的,当我们把这一个叫做深度优先讲完了过后呢,我们紧接着又给同学们介绍了图的广度优先便利的一个问题,好的。好,放这儿。啊,广度优先,那图的图的广度优先,我们介绍了这么几个部分,首先给同学们介绍了一下。广度、优先、便利的基本思想。是不是先给同学们介绍了它的基本思想,说它类似于一个分层搜索的过程,大家还记得刚才我们看这个图。
10:07
给大家看看这这个图,呃,我我就不好切了啊,就是同学们演示的这这张图,就这张图是不是类似于分层呢,对吧,类似于分层好然后呢,我们又给大家具体说了一下,广度优先便利的具体的一个步骤。是这样几个步骤,还记得吧?OK,我给大家罗列这里。好,最后这最后这一步呢,要分成三步走。对。当我们把这个做完了过后呢,我们是不是呃,也给大家好像也画了一个,画了一个图给他描述了一下,但是那个图我没有截下来,很遗憾,但是大家看这个文字哈。看这文字应该也大体能能理解好,当我们把这个广度优先说完了以后呢,我们就在用这个图形的方式给他分析了一把,分析了一把,好,这个我们也写到这吧。就是。叫广度,广度优先算法的一个图示。
11:06
对不对,是一个图示,那这个图示呢,只留了一点点东西在这了啊留留的东西不多啊,留的不东西不多,就这就留留了一个小箭头在这啊,那如果说同学们想看呢,可以把视频打开再再搂一就行了,好也不是什么很很难的事,好当我们把广度优先这块说完了以后呢,我们是不是就就把广度优先代码实现写了一下广度优先算法的代码实现。I的代码实现好的,我把这个写个二,那代码实现它主要是哪一块呢?其实就是这两个方法。是不是就是这两个方法呀,诶就这诶这个广度优先就没有切上。广度优先,我简写的叫BFS。BFS叫broad first search,它的代码呢,我给大家放到表格里面完事。
12:04
当我们把这个做完了以后,我们是不是就做了一个比对,那比对呢,我们这样子啊,最后把这个汇总代码写完,就是关于图的。图的一个代码汇总,代码汇总。好的,我把这个呢也放到这,大家要看整体的代码,就直接从这拿就可以了,好的,我把这个图整体拷贝到这边来。没问题吧,同学们挺简单哈,放这那这个做完了以后,同学们也有发现一个问题,就是说根据老师给的这个图,好像广度优先和深度优先一模一样,所以说为了让大家感觉到有区别呢,我们又给他讲了一个图的深度优先和广度优先的一个不同的案例,就是运行起来不同的案例。好,具体来说呢,我们就给大家举了这么一个小案例,对吧?诶,这个小案例就放这了,好吧,那这里我就截个图就完事了。这里我就一个图案代码,其实在上面已经有体现了。
13:03
蛋白已有体现,好,同学们,那关于这一个图这一块的内容呢,就给大家聊到这里。让大家要去深刻的理解深度优先和广度优先它的一个区别和算法的实现,小心同学们在面试的时候或者笔试的时候,人家让你写一个方法出来。对不对,所以有些他不让你写方法呢,他让你问你深度优先和广度优先区别是什么。是不是深度游戏市场有点像纵向往下走,广度有些它是横向的,就是一层一层的来进行这么一个便利啊,具体来说代码里面我们都已经讲过了,好的,那关于图我们就跟大家聊到这里。
我来说两句