漫画：深度优先遍历和广度优先遍历

旧城等待， 2023-07-17 09:57 33阅读 0赞

![format_png][]![format_png 1][]

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

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

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

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

**什么是 深度/广度 优先遍历？**

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

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

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

![format_png 15][]

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

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

![format_png 16][]

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

![format_png 17][]

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

![format_png 18][]

像这样先深入探索，走到头再回退寻找其他出路的遍历方式，就叫做**深度优先遍历（DFS）**。

![format_png 19][]

![format_png 20][]

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

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

![format_png 21][]

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

![format_png 22][]

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

![format_png 23][]

像这样一层一层由内而外的遍历方式，就叫做**广度优先遍历（BFS）**。

![format_png 24][]

![format_png 25][]

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

![format_png 26][]

![format_png 27][]

**深度优先遍历**

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

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

![format_png 16][]

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

![format_png 17][]

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

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

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

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

![format_png 28][]

从顶点8退回到顶点7，顶点8出栈：

![format_png 29][]

接下来访问顶点10，顶点10入栈：

![format_png 30][]

从顶点10退到顶点7，从顶点7退到顶点1，顶点10和顶点7出栈：

![format_png 31][]

探索顶点9，顶点9入栈：

![format_png 32][]

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

**广度优先遍历**

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

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

![format_png 21][]

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

![format_png 22][]

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

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

首先遍历起点顶点0，顶点0入队：

![format_png 33][]

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

![format_png 34][]

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

![format_png 35][]

然后顶点2出队，没有新的顶点可入队：

![format_png 36][]

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

![format_png 37][]

![640?wx\_fmt=jpeg&tp=webp&wxfrom=5&wx\_lazy=1&wx\_co=1][640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1_wx_co_1]![uploading.4e448015.gif][]转存失败重新上传取消![640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1_wx_co_1][]

![format_png 38][]

/**
    
    * 图的顶点
    
    */
    
    private static class Vertex {
    
    int data;
    
    Vertex(int data) {
    
    this.data = data;
    
    }
    
    }
    
    
    
    /**
    
    * 图（邻接表形式）
    
    */
    
    private static class Graph {
    
    private int size;
    
    private Vertex[] vertexes;
    
    private LinkedList<Integer> adj[];
    
    
    
    Graph(int size){
    
    this.size = size;
    
    //初始化顶点和邻接矩阵
    
    vertexes = new Vertex[size];
    
    adj = new LinkedList[size];
    
    for(int i=0; i<size; i++){
    
    vertexes[i] = new Vertex(i);
    
    adj[i] = new LinkedList();
    
    }
    
    }
    
    }
    
    
    
    /**
    
    * 深度优先遍历
    
    */
    
    public static void dfs(Graph graph, int start, boolean[] visited) {
    
    System.out.println(graph.vertexes[start].data);
    
    visited[start] = true;
    
    for(int index : graph.adj[start]){
    
    if(!visited[index]){
    
    dfs(graph, index, visited);
    
    }
    
    }
    
    }
    
    
    
    /**
    
    * 广度优先遍历
    
    */
    
    public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) {
    
    queue.offer(start);
    
    while (!queue.isEmpty()){
    
    int front = queue.poll();
    
    if(visited[front]){
    
    continue;
    
    }
    
    System.out.println(graph.vertexes[front].data);
    
    visited[front] = true;
    
    for(int index : graph.adj[front]){
    
    queue.offer(index);;
    
    }
    
    }
    
    }
    
    
    
    
    
    public static void main(String[] args) {
    
    Graph graph = new Graph(6);
    
    
    
    graph.adj[0].add(1);
    
    graph.adj[0].add(2);
    
    graph.adj[0].add(3);
    
    
    
    graph.adj[1].add(0);
    
    graph.adj[1].add(3);
    
    graph.adj[1].add(4);
    
    
    
    graph.adj[2].add(0);
    
    
    
    graph.adj[3].add(0);
    
    graph.adj[3].add(1);
    
    graph.adj[3].add(4);
    
    graph.adj[3].add(5);
    
    
    
    graph.adj[4].add(1);
    
    graph.adj[4].add(3);
    
    graph.adj[4].add(5);
    
    
    
    graph.adj[5].add(3);
    
    graph.adj[5].add(4);
    
    
    
    System.out.println("图的深度优先遍历：");
    
    dfs(graph, 0, new boolean[graph.size]);
    
    System.out.println("图的广度优先遍历：");
    
    bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>());
    
    }

![format_png 39][]

![format_png 40][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29sdXR2eXBIbnE5TFpFSjZYaGxvbGEyN0xIVG5vZ0tKemYwVlF2cTUxSUNHSXNJZ2pud1RNVWlicGlhYlJQeXZKWVFvaWJWRGh6SnpoM0EvNjQw?x-oss-process=image/format,png
[format_png 1]: /images/20230528/16b129b058b545d1842a601fb45e6ab0.png
[format_png 2]: /images/20230528/bd349cab82c64ddf806f06001a1495df.png
[format_png 3]: /images/20230528/c52a2f1d795f4f409d3366274115521a.png
[format_png 4]: /images/20230528/b89caad28f0446f280e5bddfc1a882ca.png
[format_png 5]: /images/20230528/489b7fb7112f480e91df4c030a08d1ab.png
[format_png 6]: /images/20230528/dee98f6a2eb44c3d9a175e27baeb978c.png
[format_png 7]: /images/20230528/f7dfc6da0f1b47faa2e4358814c2a354.png
[format_png 8]: /images/20230528/1bcde999f0df4bf2b6ee8968fe1763a6.png
[format_png 9]: /images/20230528/507d3b5573904f768270ffa4a36d36de.png
[format_png 10]: /images/20230528/100790fc1fa34841a04d9b6656f1ca90.png
[format_png 11]: /images/20230528/8bfe3d1ee5684cd786fd598384e545ae.png
[format_png 12]: /images/20230528/cabde91bb2a24b89aba6ad911874a8ba.png
[format_png 13]: /images/20230528/fcb3bc0803c44e0b8bc83be525a44aed.png
[format_png 14]: /images/20230528/395b7448a8f74566ac261d61ceb80450.png
[format_png 15]: /images/20230528/98f2bf6e92a14a15995301a546f9311b.png
[format_png 16]: /images/20230528/26831d1dfc1e4b5d9fdfcc34a8d87279.png
[format_png 17]: /images/20230528/212bf02d1bf3492b8fb832c8560f459d.png
[format_png 18]: /images/20230528/1c3ea03bba3c4abf8c5fa43040db8218.png
[format_png 19]: /images/20230528/d150722c38de4319bfa017ebe4129466.png
[format_png 20]: /images/20230528/1e6feabac5c64c5aa57844a14642b25b.png
[format_png 21]: /images/20230528/16ad1d532abb449680b7356da9357b3e.png
[format_png 22]: /images/20230528/745fa2ee5e024e02a1660ae1969531bd.png
[format_png 23]: /images/20230528/e86473865fa6428aa739d0bad8f8f3ef.png
[format_png 24]: /images/20230528/e6dcb2d7ec1547b2a396456fd4700e18.png
[format_png 25]: /images/20230528/cd033be8115f4b9592586b00f5d1f938.png
[format_png 26]: /images/20230528/ae4e0180d2b746a59216b7e44e2a0a75.png
[format_png 27]: /images/20230528/0ee0b7642bbe4dbf9725120521a335af.png
[format_png 28]: /images/20230528/bf987541b8524d289d6d5ab51931c9fc.png
[format_png 29]: /images/20230528/e7da1235e807446cad2f6aa25177f02f.png
[format_png 30]: /images/20230528/c51a5b497e2e42c0874834414da129d7.png
[format_png 31]: /images/20230528/8f1643e21f124c2d8af5c6e5e5f4a038.png
[format_png 32]: /images/20230528/c4c74617c7ea4d228c8d6c47a3ab7e79.png
[format_png 33]: /images/20230528/0ed2953d5dd646d9ad8ff9bb5ec38175.png
[format_png 34]: /images/20230528/56e28482fe8a489984d9f66076953d2c.png
[format_png 35]: /images/20230528/4b1ea7d961a547fba991d60ebec2290b.png
[format_png 36]: /images/20230528/c3b10c9d8e8f43c6a3609f1555d3b2d1.png
[format_png 37]: /images/20230528/47ffb7c4af4d413aaef4d59fc39b7575.png
[640_wx_fmt_jpeg_tp_webp_wxfrom_5_wx_lazy_1_wx_co_1]: /images/20230528/d18a29c079dc498face0981dbf628a20.png
[uploading.4e448015.gif]: https://csdnimg.cn/release/mp/img/uploading.4e448015.gif
[format_png 38]: /images/20230528/074649040c914b51aa914b4ad808c50c.png
[format_png 39]: /images/20230528/befa976d2cc8413089c30d90bfb8a516.png
[format_png 40]: /images/20230528/9bd2ee5f54d34c9abc932494d35b3cb7.png