淘先锋技术网

首页 1 2 3 4 5 6 7

专注于Java领域优质技术,欢迎关注

来自: 程序员小灰

dfbd1ccde1ae04fc0b06df0b06ba3312.png
6065a7a37e273aac83f473642ee98682.png

————— 第二天 —————

0325fdb76d3c93ecfed155b71eea2944.png
5ca244a5441bbb60c2a94c613fd6c552.png
3ce7a858e3ecee442607fb7f728ff8cf.png
59351ee02b2094c342b599376a7843b7.png
46f56e346a0f386c971d6547f737d64f.png
0c057925a7f2b378393fbf27ca2caefe.png
6fa0520a5b1d6a1b1392eb8b880724d3.png
869a86f3-512d-eb11-8da9-e4434bdf6706.png
d0fefbec0c8ce443b2fc7e231f94a61a.png

————————————

6d92ab93d0e17ed1c780fbff290b8aee.png
8d9a86f3-512d-eb11-8da9-e4434bdf6706.png
aedb3b85a2f876682507d1603e30b55a.png
b0f57e1b65a5f7a5bed5e9b08f71a322.png

什么是 深度/广度 优先遍历?

深度优先遍历简称DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

这两种遍历方式有什么不同呢?我们来举个栗子:

我们来到一个游乐场,游乐场里有11个景点。我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?

8f4c4872661550feb53a2aed099ec5dd.png

第一种是一头扎到底的玩法。我们选择一条支路,尽可能不断地深入,如果遇到死路就往回退,回退过程中如果遇到没探索过的支路,就进入该支路继续深入。

在图中,我们首先选择景点1的这条路,继续深入到景点7、景点8,终于发现走不动了(景点旁边的数字代表探索次序):

c57b61c3a20e18ca8b6ca73927f9e20f.png

于是,我们退回到景点7,然后探索景点10,又走到了死胡同。于是,退回到景点1,探索景点9:

2d35bf2bc8de55a5422eb9cbc802ed13.png

按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、6,终于玩遍了整个游乐场:

241443e533856d18b39aa63b9c8f2a6a.png

像这样先深入探索,走到头再回退寻找其他出路的遍历方式,就叫做深度优先遍历(DFS)

64a09fada187ae440c2b65bbc1a6f3d2.png
974f484c7c9aded27cdc031e572715fb.png

除了像深度优先遍历这样一头扎到底的玩法以外,我们还有另一种玩法:首先把起点相邻的几个景点玩遍,然后去玩距离起点稍远一些(隔一层)的景点,然后再去玩距离起点更远一些(隔两层)的景点......

在图中,我们首先探索景点0的相邻景点1、2、3、4:

0afff94d60ea2f90d7e6bf459822ff21.png

接着,我们探索与景点0相隔一层的景点7、9、5、6:

60afb29652343eba7c622c7c225de2d2.png

最后,我们探索与景点0相隔两层的景点8、10:

34293582c8d38dcd22c3fdc0247640d1.png

像这样一层一层由内而外的遍历方式,就叫做广度优先遍历(BFS)

9c370f61b8852c5f9b9a2a8951a49b24.png
b1e98dfec32cdc51e3d1c8d971849f15.png

深度/广度优先遍历 的实现

08b725e1b9eea48a2a9fd98c83ee5aaf.png
2a2226ef546a6d9a62e8dbe3a0f898b3.png

深度优先遍历

首先说说深度优先遍历的实现过程。这里所说的回溯是什么意思呢?回溯顾名思义,就是自后向前,追溯曾经走过的路径。

我们把刚才游乐场的例子抽象成数据结构的图,假如我们依次访问了顶点0、1、7、8,发现无路可走了,这时候我们要从顶点8退回到顶点7。

c57b61c3a20e18ca8b6ca73927f9e20f.png

而后我们探索了顶点10,又无路可走了,这时候我们要从顶点10退回到顶点7,再退回到顶点1。

2d35bf2bc8de55a5422eb9cbc802ed13.png

像这样的自后向前追溯曾经访问过的路径,就叫做回溯。

要想实现回溯,可以利用的先入后出特性,也可以采用递归的方式(因为递归本身就是基于方法调用栈来实现)。

下面我们来演示一下具体实现过程。

首先访问顶点0、1、7、8,这四个顶点依次入栈,此时顶点8是栈顶:

6ce7584d0d4e279b5042cf2204984786.png

从顶点8退回到顶点7,顶点8出栈:

1963d6ac15de8392a14fda7495156479.png

接下来访问顶点10,顶点10入栈:

8292ebc8989baa54b97d1d9737f62795.png

从顶点10退到顶点7,从顶点7退到顶点1,顶点10和顶点7出栈:

e65e777a7246e9addd3be9f5b880150a.png

探索顶点9,顶点9入栈:

182d9eae9c3d6ef3e2a4f713bedad753.png

以此类推,利用这样一个临时栈来实现回溯,最终遍历完所有顶点。

广度优先遍历

接下来该说说广度优先遍历的实现过程了。刚才所说的重放是什么意思呢?似乎听起来和回溯差不多?其实,回溯与重放是完全相反的过程。

仍然以刚才的图为例,按照广度优先遍历的思想,我们首先遍历顶点0,然后遍历了邻近顶点1、2、3、4:

0afff94d60ea2f90d7e6bf459822ff21.png

接下来我们要遍历更外围的顶点,可是如何找到这些更外围的顶点呢?我们需要把刚才遍历过的顶点1、2、3、4按顺序重新回顾一遍,从顶点1发现邻近的顶点7、9;从顶点3发现邻近的顶点5、6。

60afb29652343eba7c622c7c225de2d2.png

像这样把遍历过的顶点按照之前的遍历顺序重新回顾,就叫做重放。同样的,要实现重放也需要额外的存储空间,可以利用队列的先入先出特性来实现。

下面我们来演示一下具体实现过程。

首先遍历起点顶点0,顶点0入队:

cf51edb56ebda39f15753bdf87a8fbb7.png

接下来顶点0出队,遍历顶点0的邻近顶点1、2、3、4,并且把它们入队:

1cc401f959e74f5b1424b3bd3a018d05.png

然后顶点1出队,遍历顶点1的邻近顶点7、9,并且把它们入队:

00d924494a74ef54ea0fdd804f1383ef.png

然后顶点2出队,没有新的顶点可入队:

e891e00baad8457bf8850c32d77e7903.png

以此类推,利用这样一个队列来实现重放,最终遍历完所有顶点。

31edf98c5f2889af1fcd84e63eabf6ce.png
2c81366a880c7549f42ec7ca125aac3a.png
1dba9b5f215dbacbc41f6633691f6ae8.png
2d89a7a30832562770591df729b9b793.png
251920e313850aaefa993e00299a6680.png
882a7bd59342038080e989a11481c5c9.png
7644f7a89810af4f20b45d9f4814d241.png
4f5281882908c1f762daabefd753eeb8.png