00:00
同学们,我们来实现一把这一个图的广度优先便利,那首先呢,我们其实是按照刚才的整个这个分析的六步,先把放用广度优先来把第一个就说一个节点的广度优先做完。然后再用一个for循环把它把所有节点。For循环一把,这事就结束了,也就是说现在我们要把这六步啊,六第六步下面还有三步,把它翻译成我们的代码,大家同学们注意听我的这样一个过程啊,并不难,大家不要觉得这个很难,不要觉得这很难啊,来咱们玩一把。老规矩,来,走一个代码在这儿写。我们先写什么呢?A编写一个广度,就是说应该说对一个节点进行广度优先,优先便利的一个方法啊,你看我这写的是对一个节点,那也就是说那你有五个节点,你会怎么样呢?你还用for循环。
01:01
把这个方法套一下才行,好大要要认真听哦,好,那现在我们还是写成一个私有的,跟刚才一样,VO broad。啊,广度的意思,那么就叫BFS吧,简单一点,那同样道理,是不是我们仍然会有一个数组,就是不数组表示是否访问过V的,OK,然后呢,我们要把这个I传过来,就是代表你对哪一个节点进行进行一个广度优先,便利。好了,那首先呢,同学们可以看到我们这边会有个U,这个U代表注意听我们是不是到时候会根据我这个设计,我会去取出这个队列里面的一个头节点啊,所以说这个U呢,我先取出来,先定下来这个U,注意听这个U表示表示我们队列的一个头节点,头节点对应的这个下标能理解吧,实际上我们就是求求的这个节点的下标,我们没有真正的把这个ABC放进去,我们是把ABC对应的下标放到我们这个队列里面的,理解吗?好,还有一个W,好,这个W当然就是我们要在整个过程中会去找的。
02:15
这一个节点的下标就是这个W,就相当于是临接点的临界点的临接节,临接节点的这个下标明白表示临接节点WOK就写到这那下一个。因为你在整个过程中,我们还需要一个数,需要一个队列是吧?需要一个队,为什么需要一个队列呢?因为你需要这个队列才知道到实验,我是从就是刚才我画的这个图到实验,我是从当我这个A走走不当我这个A访问不到D的时候,我是从B开始去走呢,还是从C开始啊,所以说我我得有一个队列把把这个A进行这个广度编辑的时候,把它顺序记录下来,明白我的意思吧,好,这里面有个队列,这个队列呢,我说一下这个是节点队列,就是就是是节点访问,访问的一个顺序记录啊,相当于说它是记录节点访问的一个顺序,能理解吗?
03:15
好,那我现在用什么呢?各位同学,我简单一点,我们直接用一个link的list。OK,这个link的list呢,呃,它是它就可以当成一个队列用,为什么呢?因为它有两个方法,一个是爱last,还有一个remove first,好,就所以说我就用它了,明白好,为了嗯比较好写,我就叫就写个叫Q。好,同样我把这个包包引进去,好,咱们就OK了,那紧接着呢,我们继续往下写,就是刚才讲过,当你到这一步的时候,你上来过后,就只要走到BFS,就代表这个节点我是可以访问到的,是吧,所以说我就先干什么呢,访问这个节点明白。访问节点。
04:00
注意听啊,这个稍微有点麻烦,访问这个节点,访问节点其实就是输出这个节点的信息嘛,对不对,节点的信息那很简单,我就还是不打不换行了,好吧,我们就get value。Get这个value by index I放进去。那么为了好看呢,这呢,我仍然去给它一个箭头,好吧,好,访问完了过后还记不记得你要把它标标记为标记,为什么呀?标记为已访问,是不是已访问。乙。访问。OK,那这个很简单吗?跟刚才一样,Is visited,把这个I放进去,写成一个处。因为你已经访问过了,那访问完了过后,下一步我们有一个动作要把什么呢?将这个节点加入队列,为什么要加入队列啊,因为我我不是我不是刚刚讲过吗?这个队列就是记录节点访问的顺序,你不把它加进去哪行了,对吧?所以说我就QQ加队列一定要注意是A拉哦,我们知道队列它有个特点是呃,加的时候是从尾部加入,取的时候是从队列的头部取,是不是同学们。
05:15
好,那这个怎么加呢?其实就是把这个爱加进去,对吧,这就搞定了,加进去过后好了,同学们现在呢,就开始按照刚才老师说的一个循环的过程来玩吧。对不对,只要这个队列飞空,我就继续的做这个事情,好的,那就写句Y循环,只要飞空,那A。只要他这个队列飞空点什么呢?Is empty,这就用到我们以前学队列的一些知识了,是不是同学们?好,只要你不为空,我干什么呢?各位取出队列队列的头。头节点下标是这样子的,同学们,那怎么取呢?Very easy Q点remove first,看到没有它remove first就是把这个队列头的这个这个数据取出来,取出来同时把它删掉了,肯定要掉才有意义嘛,好,取出来过后呢,很遗憾它是一个object,我们不能用一个int接收,也就你把这个U传进去,它报错,类型不匹配怎么办呢?把它转成一个integer。
06:22
对不对,但inte呢,诶这这就可以了,它自动的一个什么呀,拆包是吧,Inte完了之后交给U,这个叫自动拆箱功能,是不是同学们好的。把它取出来以后,同学们,那现在呢,我们再把wa取出来。W,怎么写呢?现在现在根据前面这个角,我就要,我就要得到。我就要得到什么呀。得到注意听根据前面我们讲的这个流程,我们要得到他的这个得到第一个临界点的下标W。
07:00
就是我我要看看他能不能去这个去访问嘛,所以说这一门我就是。W,怎么取呢?Get first。对,我要get first neighborhood,那这个地方就是我们U。就是我要以这个U为我们的这个访问的顺序来做,其实大家想第一次进来,这个U其实就是A节点对应的下标,也就是他相相当于他现在广度编辑,就是说先先让这个A以A这个节点看看他能访问成什么,全部访问完明白了吧。诶,待会我们再debug一下大家大家就清楚了啊,不要着急,因为这个代码是广度优先,还有深度优先,都有一定的难度,好,我把它取出来,取出来过后就要判断了,根据刚才我们讲的,你取出来这个W到底到底存在还是不存在呢?存在我们还要看有没有访问过,是不是这个道理啊,那就应该这么写了,W如果不等于负一,说明什么问题?各位同学。说明你这个呢是找到了。
08:02
找到,也就是说你是可以连的,可以连的,那如果是可以连的话呢,我要判断是否返还购是否。访问过,是这样子吧,同学们,那就写if语句,如果说如果他没有访问,我们才去,才去处理吗?那就是W。如果他没有访问过,OK,这时我们就要进行这三部曲,哪三部曲啊,第一步。是不是就把它访问并标记为已访问,这个简单,那就是输出嘛。输出这个信息就跟刚才一样的,把这个打出来就可以了,是这样子吧,同学们。OK,我把它全屏一下好吧。OK,那取出来以后呢,我们下一步要标记,标记已已经访问,能理解吧,那就是一是e visited的谁呀,现在是W吧,要把它写成一个除。下一步还要干什么事情?入队列?为什么要入队列呢?因为这个已经被你访问了呀。
09:04
对,你已经访问了,我就要把它的一个访问顺序记录下来,那为了记录下来有两个作用,当我在某个位置找访问不到的时候,我就要从队列里面取出一个,从队列头取一个,看看它能不能访问呢?是不是这个道理啊,好,这个就要加入队列,能理解吧?啊,有点稍微有点麻烦啊,那一定是要at last,不要写错了啊,同学们。你是往队列屁股后边加啊,你先别千万别加错了。这个就放进去了。好了,那如果说你取的时候它已经访问过了,怎么办呀。各位同学,如果说他已经访问过了,你是不是应该这样找?按照我们刚才这个这个这个线来说。假如。已经访问过了,是不是我还是要以这个A节点去找下一个呀?去找你访问过的这一点的,下一个能理解能理解这意思吧,就是说如果访问过干什么呢,就是以。
10:04
以这个UU为我们的这个这个起始点,以以U啊,这怎么描述呢,就是以U去。呃,为为前一个节点。为前驱啊前驱。前驱就不好写前驱点。找什么呢?找W后面后面的啊,后面的这个。第一个节点啊,你W后面的下。一个零临界点,大家知道我在做什么事吗?其实说白了这句话就是说如果在这个过程中,我发现有一个被绑了,比如说我我在用A去做的时候,我访问访问,诶访问到访问到这个C,呃是可以,我们是有连线的,但是呢,他已经访问过了,怎么办呢?我还以这个A点,还以这个点开始去找C的下一个这个D,我有没有访问过,是这意思吧。
11:06
其实这句话就在干这个事情。那怎么写这句话呢?其实我们以前写过的就是get next。Get next。Ne,但是这个第一个U就是你,你的这个U,下一个就是W,这句话就是找EU这一行的W的下一个临界点,我这其实叫前驱不是很准确啊,不是直接前驱,不,不是它的直接前驱,它可能是已经是,呃,已经是他的上一级前驱都有可能,好大家理解一下,好拿到这个W再去看W是不存在,然后再访问这个地方,就这个地方就体现出什么了。这个地方就体现出我们的广度优先。是这样子的吧,同学们,哎,你看这个地方就提出我们广东优先的一个很经典的一个算法了,很经典一个算法。对,因为你说是U嘛,我我不去往下一个节点走跑。
12:03
好了,那这个走完了以后呢,我们我们这个这个代码应该就好像是写完了似的是吧,我看看啊,只要不为空我就取,取完了过后就Y循环,Y循环过后取出它下一个就是U。为全区节点,再在这个U的U的这个基础上再去走,看看他下一个能不能找到,好,而不是跳一个,而不是跳一个好了,嗯,这个应该好像是没什么问题吧,有问题我们再调吧,好吧。那现在呢,我们讲了刚才写的这一个广度优先算法,其实仅仅是针对什么呀,一个节点而言的。但是你有没有一种可能性,你一个节点是不行的呀,所以说我们还得写一个方法,这个方法呢,就是要这样子的,就是要便利所有的节点啊都进行,进行什么呢,广度。
13:02
A、广度优先。搜索啊,广度优先搜索。OK,那这个代码呢,就跟刚才原先写的很类似,VO broad,我我就对它进行一个。进行一个重载,重载就行了。广度优先优先BSF,我看这个名字BFS啊,咱们别写错了。好,那这个时候我们就是不是上来过后,我们就进行这样一个循环,N ti等于零,I小于我们。整个这个节点的个数,是不是因为我所有节点我都要走嘛,所以说应该是这样写的是get。我们看这里写的有number of。A vertex,是的,然后I怎么样加加,各位朋友,爱加加爱加加完了过后,首先还是老规矩,如果你没有访问过。
14:06
因为我在进这个处理的过后,我还是要判断你有没有访问过嘛,如果说你这个点没有访问过,我才去做这个广度优先搜索,那这方就应该是。我们的一个便利,把is visited放进去,再把我们哪个放进去呢?I放进去代码就写完了。待会就写完了,好,同学们,我们来玩一把,看看整个过程对还是不对啊,待会我们再debug一下就可以了,来,朋友们。试一把。那现在呢,我们来写一个叫做广度。诶,广度优先明白广度优先好的,那我CS。点什么呢?BFS。好,各位同学,我们看如果它不出问题的话,它的顺序仍然是ABC。D。E是不是这样子的同学们,我们运行车。
15:02
后门运行完了后发现呢。这个地方再再运行一下,看为什么顺序不对哈。大家看。他是这样子,我们这换一行。幻想这样好看一点,好,同学们好的。这样晃一晃,大家看起来比较舒服一点。诶,这个为什么这样子的啊,因为他打印的顺序,因为广度优先,他这个便利的时候他花时间,所以说他有可能是下面这个先打出来的,再来走一下。好,这样看,我们看到深度优先还是abcde,但是广度优先啥都没有,是不是为啥呀,同学们,哪个同学能告诉能想一想为什么呀,原因是什么呀?是不是因为你在做广度优先的时候,你已经把这个我们的这个。Is visit的这个数组都已经复制的差不多了是吧,都全部为触了,那肯定他走不了了嘛,所以说如果你要做这个测试的话呢,那你就不不能先掉这个深度优先,你掉了深度优先,那不是他都已经跑了一圈了,已经把你的这一个数组全部支撑支撑这个处了,那就没法玩了是吧。
16:10
如果说你你看啊,如果我把这个注销这个就没问题了,你看我注销一下。我注销,你看这个广东优先,诶大家看广东优先,为什么还是这样子啊,我看看是不是哪个地方输错了。不着急啊,不着急,好,广州有线还是有毛病,我们来定位一下。我把它定位一下,哪个地方写错了,揉一圈。好,我们来看看哪地方代码写错了呢?很好,很好办,我们捋一捋思路,一会就能解决,对吧?写代码有问题是很正常的,看看哪个地方有问题。捋捋。看一下吧,各位同学。看一下啊,嗯。我们看一下,再再再看看这个运行结果吧,看再再看几期结果,A全A,那全A这个没有道理对吧,我们看看,那肯定是咱们在进行输出的时候出了问题,因为算法没有什么毛病。
17:05
往下看。呃,我们在输出的时候,其实就这个位置输出I是没问题的,I进来就输出这边是WW,对那哦大家看这地方写错了,应该是W对吧,你你因为你这已经取出的是W嘛,那显然输出的也应该是W,而不应该是I,就这么一点小问题。好,我们我们再来运行把同学们。大家改完了过后看效果,诶大家看abcde就正确了。呃,深度游先,因为我没有去掉,所以说这个顺序就没有毛病了,Abcde正确的,那这样子我们呢,还是用刚才原先我们debug的方式,我们来验一下,注意听啊,这这个验证的过程还是挺重要的。验证的过程还是挺重要的,我再补一刀,有些同学说,老师,那如果我又需要走这个深度,又想走这个广度,两个都想走怎么办呢?那也可以,你要你要一定要这么做的话,你可以这样干啊,同学们听我说,嗯,如果你一定说我我无所哪个都要,哪个要做的话,那你就把这个初始化工作怎么走呢?
18:11
你把这个初始化的工作不要放在构造器里面了,你放在哪啊,郭同学,听我讲,你进行这个。这个深度优先的时候,你把它。置一个空。再进行我们这个广度进行搜,搜索一下也是一个空,这样子你就随时随怎么调都可以了,为什么呢?因为你上去每一次调用它都是新的,所以说你你这样子就没有任何问题,看啊同学们看。是不是这些都被,诶我们再这样输出一下。你看这个都没毛病吧,深度遍历abcde啊,广度优先也是这个abcde是吧,那现在这样子,我们呢,给同学们来测试一下,广度优先搜索它是不是跟我们刚才整个这个分析的是一样的,注意听哈,来各位朋友我们DEBUG1把。
19:05
Debug来,跟着我的思路debug一下,其实大家就心里面特别清晰了。来看一下。首先我们代码呢,已经执行到了这里,我追进去。追进去过后,同学们可以看到,诶,看这门追错了,直接跳进去了,重新来啊,重新来。这么追错了?我们。我们重新来追这个追错了啊,追错了,追错代码了,好,我们应该是在这来追,把这个代码切过来。好。我们把。把这个断点下到这儿的来,同学们,我们运行一一把。对吧,我们运行一把。好,DEBUG1项。Debug一下。啊,我们先把这个关闭,有些不要的,先把它关一下,关一下我们第八个一下重新来。第八个。
20:03
好,第八个项。那现在debug过呢,我们追到这个里边去进去好,进去过后呢,首先我们把这个。就是表给制制成空的了。就是把我们这个数组制成空的下一步轴。好,进到这里面第一个I显示零,接着往下走。好,我们追进去,追进去过后我们可以看到呢,此时此刻他先创建了一个link list,这个没有问题,现在就输出A了。没问题,把输出A输出A往下走,现在把这个A加入到我们队列里面去了,A里面有个零正确的,因为代表第零个下标已经被访问,现在我们的队列不为空往下走。好,此时此刻把这个A取出来,取出来的目的呢很简单,就是要去找A的下一个这个临界节点的下标,那么下一个临界节点下标到底是有没有呢?一说明它下一个跟下一个临界节点其实是可以通的,那这个时候呢,他就进去发现下一个节点W等于一,显然就是B,好,这时呢,它就会。
21:11
进去把这个B输出,把B输出过后,把这个BB这个节点标记为已经已经访问过,再把B加进去,注意啊,这个时候大家一定要记住,这个时候加进去过后,我们这个队列里面只有一个B哦。只有B对应的下标,哦,好,紧接着呢,也大家看到这里没有,他把这个事情做完了以后,你们有没有发现他这个时候是在尝试着找A。A的就是A,以A这个为前驱,找A的这个,B的后面这个节点,实际上是是在找谁吗?实际上大家看。这个时候在整个这个过程中,注意听,整个过程中他先找的是谁呢。这个get next ne他也是从第零个开始找的,所以说这个时候他找了个W,你们看是谁是二。
22:05
是不是二啊,是不是就是二,这个是二往下走,这个二就是C嘛,C也没访问过就进去了。C被访问。C访问。那C被访问过后,又把这个C加到我们队列里面,大家想注意听,这个时候是不是我们队列里面其实有两个,一个是一个是二,其实说白了就是一个B,一个C已经被访问了。好,这个时候他继续以这个追星,他继续这个U还是零,这个W是二,其实他现在尝试着去找哪一个呢,就是说他去找。A。A和哪个点是不是通的呢?a.ABC就是和D,就是他去找A和D是不是通的,这个时候W返回来就就是几呢?大家想一想。这个时候W反过来肯定。就应该等于负一了。为什么呀?
23:00
因为你A和D它不通了,它不通怎么办呢?同学们看,这个时候它就很神奇了。诶,你看到没有。当它不通的时候,它不通的时候,也就是这个while循环。他就不走了,他不走过后,他看看有没有空,也也就是说他只要这个队列没有空,他就从这个队列头部弹一个,大家弹弹出来,这个U变成几了呢?这个U其实就就应该是一了。这个一其实就是指向那个B的,然后这个时候它是以B为这个点,又去找B的下第一个临界一点,那么这个时候B它找的是谁呢?他是找的以B这个临界点,那也就是说他应该找的是谁,可以告诉大家他找的就是这个。这个值。实际上他是找的,他说AB的以B的第一个临界节点不就是A吗?这个时候它应该返回零,明白吧,W应该返回零。是不是零呢?你看是不是零就是零。但是很遗憾,当然这个零它不等于负,它就进去了,但是很遗憾,这个已经被访问过了,所以说它就会跳过去,跳过去过后呢,诶,你看到没有,他又去找谁呀。
24:10
哎,他又去找,又在这个基础上,就是同学们看到他刚才呢,已经是以B点去找到A了。但是这个时候A虽然是找可以连通,但是已经被访问了,没有意义了,他就去找这个找下一个,但是这个零它是跳会跳过的,为什么呢?因为零它等于B和B之间是零嘛,它就直接跳过,好它就找到C了,也就是说。也就是说如果不出什么意外,他这个W返回的就应该是什么,我一执行这个W应该返回一个几呢?应该返回一个二,就是C2,我看是不是二啊。哦,先找到这个B,在这个跳过去找到,找到这个C啊,应该是返回一个二,是的,应该是返回一个二。好,是不是二呢,看。的确是二,但是非常的遗憾,二它也是被访问过的,是不是它又跳过去了,跳过去这个时候U仍然是一,W呢,是二,相当于说找找找这个找找哪个了呢?这个只能画图啊,这个语言不知道怎么描述了,找这个诶,非常的very OK,这个时候他找到B的后面这个D是可以通的,于是这个D你看啊,往下走,这个时候W返回的是几呢?往回是三往下走,好,非常非常幸运,这次这个山没有被访问过,他进去把这个地打出来了。
25:34
把D打出来过,又把D标标记成已经访问过的。再把。哪个加去,再把D加进去,再把D加进去过后,好,紧接着他继续找,这个时候有没有变。这个时候U没有变,于是他继续找这个E,这个时候就应该返回几呢?各位同学返回四了。哎,你看是不是四号,同学们是不是好,各位同学四走,看到没有四,这个四没有被访问过,好标记围巾再把四加进去,好,这个时候就要开始回溯了,因为这个点已经全部访访问完了,看往下走。
26:08
W,这个是几啊,负一好,直接跳过去。跳出去这个队列是不是一个一个的弹呢?所以它进来把这个队列头取出来,取出来过后呢,得到它的点,得到它点。走,但是大家想啊,这个时候还有意义吗?反正这个地方它会转一圈,转一圈过后,因为所有的节点都已经被访问了,他相当于在这不停走,最后就退出我们这一个。退出我们这个BSD了。啊B啊BSF了BSF退出来过后呢,但是你不要忘了啊,你不要忘了啊,他还要去走下一个节点。那下一个节点,他又走了一圈,过后发现仍然是。这个嗯,都都已经反问过了,他相当于说白走一圈啊,白走一圈,但是呢,因为我们这个点比较少,所以说会出现这个情况,如果点比较多的话呢,就不再会出现这个问题了,明白我的意思吧,你看这个你会你会不停这样去处理好了同学们,那关于我们这一个图的广度便利的一个实现方案呢,就给同学们讲到这,大家看看。
27:15
对这个有没有一定的理解,好吧。好,那下面呢,我们还要给大家说一点其他东西,就是同学们有没有发现,可能有些同学听到这说,诶,那韩老师这个广度优先和深度优先也没有看到有什么区别,不都是abcde吗?注意啊,这主要是因为我们这个图它比较简单,待会呢我再给你们看一个图。我们再举一个例子,你会发现,诶,确实区别还是很大的,好吧,我们下一个视频再把这个图的深度优先和广度优先做一个比较,用一个案例来说话。
我来说两句