同学们好，今天我们来讲讲广度优先搜索。 我们从简单的题目 抓住那头牛开始，这个题目说的是 有一头牛，如何知道这头牛的位置， 怎样抓住它？农夫和牛都在数轴上面， 农夫的起始位置坐标是N，N是0到十万之间，牛的位置是在 坐标K的地方，K在十万范围内，然后农夫可以移动，他有两种移动方式， 一种移动方式就是从X移动到X-1或者X+1,等于说每次移动一步，每次 移动1，向左移动1或者向右移动1，这种移动每次花费一分钟，然后 这个农夫还可以跳着走，还可以从X跳到2*X的位置，这种移动也花费一分钟， 我们假设这个牛傻傻的站在原地不动，就问，这个农夫最少需要花多少时间才能抓住牛？ 那也就是说农夫需要移动几次？对吧？移动可以向左移动向右移动，跳， 一共要移动几次才能抓住这头牛？ 那好，那我们不妨假定这个农夫他 开始在坐标3的位置，牛呢在坐标5的位置， 然后我这个整个数轴最右边的范围就是6，这样问题就简单一点。 这样我们怎么找到一条从3这一点走到5这一点的路径呢？ 那在这里我需要把这些我们所关心的点它们之间的关系给它 画出来，如果有两个点之间它有一个双向箭头连接比如说2和3之间有一个双向箭头连接， 那就意味着我们从3走一步就可以到2，从2走一步也可以到3， 那有的两点之间是有一个单向的箭头连接，比如说，3和6之间，那就意味着3走一步就可以到6， 6是3的两倍是吧，它采取跳的走法，它一步就可以到6，但是我们6没有 办法走一步就到3，那3和4之间互相走一步就可以到达， 那2走一步可以到达4，但是4没有办法走一步跳到2， 那现在我就各个点之间可达的关系就画在这了。现在我们还要在这个图上面 找一条路从3走到这个5，要找这样一条路。 那我们怎么找呢？我们有深度优先搜索，和广度优先搜索 两种策略，我们先说说深度优先搜索。 深度优先搜索它说的意思就是我们从起点开始然后从每个点要往 下一点走的时候我都是随机挑一个方向就走了， 只要能往前走我就往前走，直到走不动为止， 那就回溯，那我们举， 什么叫回溯啊，就是我接着往下走走不动那我就退回几步，然后从 还能往前走的那个地方再往前走， 那当然我们在这个行走的过程一定要注意就是已经走过的点你肯定不能再走，对吧， 所以说我们要判重这个点，已经走过了我们就认为就重复了， 不能再走。好那么我们采取深度优先搜索的策略的话我们怎么从3走到5呢？ 我们从3出发，我们是随机挑一个点走的，对吧，可能我运气比较好， 我挑了4这个点，然后4再接着往下走，就走到5， 哎任务就完成了。或者我挑了6这个点，又再往下走走到5，任务也完成了，问题就解决了。就这个运气好的情况。 但是也可能运气不太那么好，对吧，因为我从3出发的时候，有2,4,6可以走， 我是随机的挑一个点，比如我如果挑了2这个点，好我们就到达2了， 然后从2这个点再往前走的时候呢我也是随机挑的， 我可以选择往1走也可以选择往4走，假设我选择往4走吧，这运气还不是太坏， 然后到达4这个点呢，我就只能再往5这走了，哎我们走到5的时候，这个点， 那有可能运气更坏，比方说我从3走到2，然后我从2再往下走的时候呢，我走1， 那1再往下走就走到0，到0以后就没地方可走了，对吧， 你不能说0再退回来1，因为1已经走过了所以你就不能再退回到1,了，那走到0了就没地方走了我们就怎么办呢 就回溯，我们就再回到1，我们看1除了0以外还有没有其他点可以走， 那1只能走到0，0又走过了，那从1出发再也无路可走了，那我们就回到上一层节点就是2， 我们看看从2出发有没有别的路径可以走， 1这条路径已经走过不能再走了，哎我们发现从2出发我们还可以走到4， 于是我们就走到4，走到 4以后呢我们就可以接着再往下走了，走到5，这个时候任务就完成了。然后我们就找到了一条路。 这是3,2,1,0,4,5这里面当然就有绕弯路对吧，因为你已经走到了一个什么都退回来然后再走到2， 再走到4，再到5，这就回到了iii。 那反正我们运气不太好的话如果上面这个序列找到解， 运气最坏的情况就是下面这个序列找到解， 那如果我们想要求最优解，就是用最短的路数走到这个点， 也就是这个位置，那我们怎么办呢？就得建立所有可能的这个走法， 当然在这个过程中我们可以做一些大量的优化， 比方说我已经找到一条路长度为N的解了， 那我们再往下走的过程中所有路径长度大于N的那个走法我们就不要去尝试了， 就是，这个我们在深度优先搜索后面再会仔细讲。 那总而言之，我们在做深度优先搜索的时候，也需要把这个行走路径上的点给保存下来， 那这些点呢，数量是比较少，我们用栈存节点可以，比方说 我从3走到2，走到1，走到0，在这个过程中，这4个点 都需要存起来，那这样的话0走不动了我才能知道退回到1这个点，对吧，1走不动我还能退回2这个点， 退回2这个点以后1和0不要，但是沿着2再往下走到4走到5的时候这个2,3,4 就都得被存起来，所以这个我们直接用栈来存储就可以了。 我们在后面的深度优先搜索的课程里再详细讲。 好，刚才说我们要从 3出发找一条路走到5，有两种策略，一种是深度优先搜索对吧， 那还有另外一种策略呢就是所谓的广度优先搜索了。 那广度优先搜索的做法呢，那广度优先搜索的做法呢是首先要给节点分层。 那我们这个起点就是第0层。然后，从起点开始， 最少需要N步就能到达的点我们就属于 第N层，它层号，比如说这个2,4,他们从起点出发， 它是需要一步，至少需要一步，实际上也是需要一步就能到达，那么 2,4,6他们的层号就是1，然后对于1,5这两个节点 我们从3出发走到它们，至少需要走2步对吧，需要走2步就能到达， 那这2和5它们的层号是2， 那对于0这个节点呢我们从3出发要走3步才能到， 那这个节点0呢它当然是属于第三层的，那分完层了以后做什么呢？ 我们就会依层次的顺序，从小的层到大 的层来扩展节点，而把层次低的节点全部扩展出来以后才可能去扩展 层次高的节点，所谓扩展就是把点拿出来看它是不是目标节点， 那比方说一开始第0层的点在这，扩展出来了，然后我们发现从 第0层一步就能走到的点有2.4.6也就是第一层的点，然后就把所有第一层的点都给它扩展出来，放在这， 没有目标节点，接下来我们就要找这个第二层的节点了， 那么要找第二层的节点你肯定要从第一层的某个节点出发，看看这个 节点走哪一步能到另外一个点，那个点就是第二层， 对吧，然后我们发现，这个 从2走一步，能够到1，所以1是第二层的一个点， 那从2走一步也能够到4啊，4是不是第二层的呢，当然不是，因为4前面已经在扩展第一层的时候 已经被扩展过了，所以你从2就不能再去向4这个地方看了，要看4已经重复了，前面已经出现过了， 然后我们再看，第一层的点2考察过了，然后我们再考察第一层的节点4， 那4走一步能够到哪里呢？那能回到3，这个不算，这个重复了。 那对于没走过的点来说，4走一步能够到5，所以这第二层的点5在这里，我们就把它写出来了， 那我们发现5是一个目标节点，所以 我们就走到这个目标节点，那么问题就解决了，就我们已经到达它了。 那我们知道5是第二层的点，所以 我们就知道从3走到5，一共就需要2步，那我们这个问题就解决了，对吧？ 那当然我们要注意我们在扩展的时候不能扩展出已经走过的节点，就 要判重，比方说我们从2再往下扩展的时候我们能把1扩展出来，但是跟4前面已经扩展过了，我们就不能再把4给扩展出来， 那广度优先搜索比深度优先搜索最明显的一个优点是什么呢？ 就是它能够确保找到最优解，就是说我们用广搜的办法 扩展出节点的时候如果我们已经碰到了目标节点，那我们 就找到了一条从起点到目标节点的最短的路径。 这是很明显的对吧，因为 我们从起点出发，走一步能够到达的所有的点我们都给它列出来了， 那如果没有目标节点的话你就不可能通过一步到达目标节点，对吧，接下来我就把走两步能到达的所有节点 都给它列出来了，如果这里面还没有目标节点，那它就意味着不可能 通过两步就能够到达一个目标节点，对吧，然后接下来我们又把所有走三步的节点都给它列出来， 那这样的话当我们碰到目标节点的时候是在列出的 走N步就能到达这个所有节点的时候我们就碰到了目标节点， 那我们当然知道，你想要从起点走到目标，至少是需要N步，是吧，这是很明显的， 因此广度优先搜索 在这个过程中你找到了点，也就是到达了目标节点，那你找到的这个点就一定是最优的了。 那广度优先搜索它有一个不太好的地方就是我们 可能会在解，解决问题的过程中扩展出来好多点 然后这些节点呢都需要保存起来，然后这个 这需要保存的节点往往是比深度优先搜索要多很多的，因为深度优先搜索嘛，我们就 走一条路，啊，这一条路上的节点保存下来就行了；那广度优先搜索它需要一层一层的全保存下来 这样它需要的存储空间往往会比深度优先搜索更高。 那在广度优先搜索的这个办法里面我们应该用队列去存节点。 啊，在深度优先搜索里面我们应该用栈存储节点，啊。 那我们再总结一下深搜和广搜，呃，它的不同，啊比方说这里有一个 一个图，啊，任意两点之间有连边就是互相可达，1可以走到3，3可以走到1。 那如果我要从这个起点1开，开始，呃 找一条路然后把这个所有的这个节点都走一遍 这个时候我们有两种策略，一种是 深搜，一种是广搜，对吧？那如果是深搜的话我就从每个 节点再往前面走的时候，我就随机找一个方向，只要能走就往前走，好 那我可以从1出发，我走到2，从2它可以往4走，也可以往5走，那我就走4呗 然后从4再往下我可以走到8，从8呢我可以走5,6,7，那我就选5也没关系，啊现在走到5的时候呢 在5，5再往前走走不动了，因为5可以走到2，,可以走到8，但都是重复的，所以5就走不动了。 5走不动呢，那我就得，就得回退到这个8，那回到这个8以后你不能 再走5，也不能再走4，但是6还没有走过，所以我们就可以去走6，啊，就是1-2-4-8-5-6对吧 节点口是6；那走到6以后呢，哎，6又没地，没地可走啦 啊因为，啊6不是没地可走啊，6不能退回8，但是6可以走到3，3还没走过，对吧 所以我们就可以直接到3了。 那走到3以后呢，你不能回退到1，呃，回退到1，但是呢，诶，3可以走到7，7还没走过，然后那我们就再走到7。 然后这个时候所有的点都被走过了，呃，这就是一个深度优先搜索建立所有点的顺序。 那我们也可以采取广度优先搜索的办法来遍历所有的节点。那就是先把 起点走过，然后，然后，然后去看这个 起点，走一步就能到达的所有的点，就是2,3，啊我把这两个点去看一下 也可以说把它们走掉吧。 然后我们再去找，呃，从起点出发走两步就能到达的 所有的点，那当然也就是说，从这个走一步就能出发的2,3 作为起点，再接着往下走，对吧？2 走两，从2出发走两，走一步就能到达4,5，啊，所以我们就找到4,5 然后从3出发走一步能够到达6,7，然后我们找到了6,7。 接下来呢，我们就要从这个 呃，最长的点出发再往下走了，对吧？我们先呢从4开始，诶它走一步能够到达8，我们就找到了8 然后，然后8就走不动了，对吧？前面呢跟它相连的点全部都已经重掉了 然后我们再去分析从5开始往下走又能走到哪，当然都重复了，都走不动，5,6,7都走不动 那现在我们走到8，实际上就已经，啊所有的途上的节点都看过了，也就是说都遍历完了。 深搜和广搜它的次序确实是不一样的。 好我们下面来看一下这个广度优先算，优先搜索的算法 呃，它具体实现的流程是什么样的。啊我们知道广度优先搜索要，一定要用到一个队列啊。 这个队列是什么东西？就是像人排队一样，啊 先进先出的一种结构。 这算法的第一步是把初始节点S0放到Open表中 然后接着要从Open表里面取出 队头的这个节点，Open表就是一个队列，如果Open表里面已经没有 节点了，为空，那么，而且这个时候我们还从来没有碰到过目标节点，那么 这时候我们就永远走不到目标节点了，此时就说明问题无解，失败退出。 如果Open表不为空，我们就把Open表的第一个节点，就是队头的节点取出来，我们把它放到Closed的表里面 然后我们假设这个队头的节点我们称之为节点n 然后我们要考察这个节点n它是不是目标节点，如果是的话 我们就得到了问题的解，我们就成功退出，啊我们就走到目标了嘛。 如果这个n不是目标节点，我们就要看这个n是不是可以扩展 如果不可以扩展，我们知道可以扩展啊，扩展，可以扩展就是说从n出发能够通过一步走到一些新的没走过的节点。 如果n不可扩展的话 那我们就把n直接扔掉了，然后n就放到Closed表里面，然后我们就回到第二步开头 再试图从Open表里面再找一个节点出来，看看是不是目标节点，或者说把它给扩展了 如果这个节点n可扩展的话，我们就会走到了第6步，我们就扩展节点n 就是我们找出所有的那些从节点n走一步就能够到达的这些新的节点。 啊，所谓新的节点就是说这些节点它不在Closed的表，也不在Open表里面，就是说它从来没有被走过。 那我们判断一个节点是不是新节点，结果我们称之为判重。好，现在我们把从节点n 扩展出来的那些新节点就放到Open表的尾部，也就是放在队列的尾部。 那我们把这个节点放到队列里面去的时候呢，我们可以同时把这个 节点它的指向父节点的指针，也给它塞到队列里面去。 呃，什么叫父节点呢？ 如果你从节点n扩展出节点m，那么这个n就是m的父节点。 就是说n走了一步就能够到达m，它就是m的父节点，呃 根据实际需要你可以把这个，呃，节点指向父节点的指针也塞到队列里面去 然后你或者可以把这个，一个节点它的层次编号放到队列里面去。 那比如说你从n走一步就到达m，那m的层次编号当然就是n的层次编号加1 对吧？然后起点的层次标号就是0。所以，在整个过程中每一个节点它的层次编号我们都可以算出来。 好，我们把这个扩展出来的节点放到队列里面以后，我们就回到第2步 回头，回头到这儿，试图从Open表里面再找一个节点进行扩展 那总之Open表里面如果 如果拿出来那个节点它是目标节点，那算法就成功结束了。 那这个算法成功结束它的条件跟我们前面讲的，和我扩展出来一个节点 发现被扩展出来这个节点是目标节点，算法就成功结束 是有一点差别，对吧？那它看起来会比前面那个做法要多算了一些东西。 但是这个没关系，顶多它就是把这个目标，跟目标节点在同一层的 那些节点都给它扩展了一遍而已，啊就算它们这些扩展都是没必要的 也花不了多少时间，那为了使得程序写法更加一致，更容易读懂，我们就采取 这里所说的从队头拿出，呃目标节点这种程序的ii方式就可以了。 嗯，另外我们真的，呃另外我们真的，嗯，处理一些问题的时候 在判重这一阶段，如果你去搜Closed表和Open表 通过这个办法来判重有时候会太慢了。 比如说你仅仅为每一个节点设计一个标记，就能够判断出来这个节点是不是曾经被放到队列里面过，对吧 所以在有的这个情况里面，实际上这个Closed表没什么用，啊就是我们把这个 节点取出来，从Open表里面取出来，我们有时候就直接扔掉了，根本就不需要去维护一个Closed表。好，下面 我们就来看看，呃，这个抓住这头牛这个问题里面，我们用广搜来解决的话，这个 队列，也就是那个Open表还有Closed表，它们的变化过程，啊。 那队列里面一开始就是一个Open表啦，一开始只有一个 一个元素3，那就是起点，然后这个Closed表一开始就是空的嘛，啊。 然后呢我再把3拿出来扩展，对吧？3被从队列里面拿出来了 它出了队啦，但是我们把3能扩展出来的新的节点，就是2,4,6，全部都给它放到队列里面去啦。 就是3进入Closed表，Open表里面是2,4,6 那接下来呢我们就要把这个Open表里面的头一个元素，就是队头的元素2给它 出列，并且对它进行扩展，2出列啦，然后呢，我们看到从2能扩展出1 然后我们就把1放到这个队列里面去啦。再接下来就把队头的元素4也拿出来 啊，4出列啦，然后从4呢能扩展出一个5 那我们把5给它放到队列里面去啦。 接下来就该轮到6出列了，啊，我们就把6给它拿出来 6还能往下扩展吗？不行啦，它能走到5，但是5前面已经 已经，已经这个，扩展过啦，已经在这个队列里面啦。 所以说我们就不能再扩展5啦，那6就直接被拿出来就拉倒啦。 然后接着就是1被拿出来啦 1被拿出来之后，我们把1进行扩展，能够得到一个0，我们就把0放进去。 好，再下一步就该是5出列啦，5出来啦，诶，从队头拿出了元素5，是一个目标节点 所以这个时候问题就解决啦，啊。 那我们把5这个节点存进去之后，也同时可以，可以存这个5的层次号 比如说2，那我们看，把5拿出来之后看到它的层次号2，我们就知道2是从起点走了两步到达5的。 那进一步我们也可以存5的父节点的指针，比如说存5的父节点指针是，是这个4对吧，它，它指向4 然后我们把，把4存进去的时候呢 也可以在4这个，这个位置也存了4的父节点指针就是3，那我们从这个5开始顺着父节点指针 就一直能走到起点，那也就是说等于找到了一条从起点到这个终点的这个路径。 接下来，接下来我们要看看程序是具体怎么实现的啊，这是一个N,K，然后MAXN是代表 最大的这个坐标范围，这里面有时候是以iii数组visited，啊 它是用来判重的标记，visited[i]如果为真的话 就说明坐标为i的那个点，我们已经啊这个 扩展过了，也就是说它曾经进入过Open表，然后它有可能从Open表出来，也可能还，还在Open表里面。 然后有一个结构step，这个Step的结构的 变量就代表一个坐标。 它的位置x，呃，以至以及从起点走到这个位置x 是花了多少步，就是这个Step。然后我们来一个对列，这个就是Open表，你的范畴都是这种Step的 类型的变量。那表示一个点以及，一个点的位置，从起点走到这个位置花了多少步。 然后，我们读录农夫的位置和 牛的位置，然後我们把这个位置全部初始化成0，啊。所以的点一开始都没有访问过。 接着我们把对列里面放头一个点，那头一个节点就是 Step（N,0）就是农夫的起始位置。 那从起点到农夫的起始位置当然走了0步，对吧？那现在，visited[N]=1谁明农夫占的那个点Nt它被访问过。 然後，我们就要不停的从Open表里面取出元素来进行处理，对吧？那只要这个q不是空， 我们就拿出对头的元素，啊，然後我们看这个对头元素它的，呃 坐标x是不是等于那个目标牛的位置k。 如果相等的话就说明找到目标了，对吧？ 那么我们这个，呃，s里面它还存放着从起点走到x点x一共走了多少步。 这个就，步数就是s.steps，那我们既然s.step就是目标 我们输出s.steps，这时候就是从起点走到 s.x也就是这个k花了多少步。 那这个s.steps一定就是最优减， 啊，就是从起点到达K所需要的最少步数。为什么？ 前面我们已经解释过了，按照我们这种广度优先搜索它的机制 我们找到的第一个减它就会是最优减。好，那如果这个对头的元素它 并不是这个目标节点，那我们就要做什么呢？ 我们就要把对头的元素拿来扩展，对吧？我们就看看从这个对头元素 s.x能够走到哪些新的节点。 然后，我们把新的节点给它set到对列里面去。 那当然我们就要判断啊，我们看看能不能往左边走一下。 如果我们能往左边走，而且左边那个点确实还没有被访问过； 那我们就把这个，呃，左边那个点给它set到对列里边去。 就用push push进去。那塞进去的这个点它的坐标当然就是s.x-1，对吧？ 那从起点走到s.x需要s.steps步，那我们从起点走到 s.x-1当然就需要s.steps的+1这么多步，对吧？ 然后，我要把这个，呃，我们把一个节点 把一个节点放到对列里面以后，我们就要设置这个节点所对应的访问标记。说明它已经被访问过了。 那这个是处理，呃，往左边扩展；这个是往右边扩展，就是找 右边相连的那个点，看看是不是要把它放到对列里面。那无论农夫还有 呃，跳跃的走法。那就是他可以跳到坐标走，坐标值为两倍的那个地方。所以我们要看看， 两倍的那个位置是不是能够被扩展出来。那首先，两被的这个位置它不能越界。 对吧？然后呢，它还必须是没有被访问过。如果 满足这两个条件，我们就把这个，呃，就是两倍的那个位置，啊，给它 放到这个对列里面。当然这个步数也是s.steps+1，对吧？然后把它的访问标记设上。 接下来我们就可以把这个，呃，对头的元素给它扔掉了。 那在这里我们并没有去维护一个close的表，因为没有必要， 我们从Open表里面拿出来的东西，要扔掉就直接扔掉了，我们不需要放在一个close表里面。 那在这个循环不停的作用情况下，啊， 呃，我们这个题它是一定能找到这个 解的，啊， 呃，你最笨到你一步步找总能找到，对吧？所以我们就不必考虑 这个，呃，那也就是说这个程序一定会从这个地方return，啊， 所以我们就不必考虑q为空的情况我们还要做些什么处理了。那因此这个程序 就完整了。那就还得分析一下这个程序的时间复杂度，啊。 那当然我们知道这个，呃，呃， 这个坐标轴它上面最多有这么100000个点，对吧？ 然後这个每个点呢它最多会进对列一起，最多也就出对列一次。 那等于反正每个点就最多被看一次，那它的时间复杂度就是 级别的N就是这个最大坐标的这种范围。
