数据结构与算法——广度和深度优先搜索

shmily 发布于2019-08-16 16:13 / 2482人阅读

摘要：今天就来看看基于图的两种搜索算法，分别是广度优先搜索和深度优先搜索算法，这两个算法都十分的常见，在平常的面试当中也可能遇到。

1. 概论

前面说到了图这种非线性的数据结构，并且我使用了代码，简单演示了图是如何实现的。今天就来看看基于图的两种搜索算法，分别是广度优先搜索和深度优先搜索算法，这两个算法都十分的常见，在平常的面试当中也可能遇到。

在图上面的搜索算法，其实主要的表现形式就是从图中的一个顶点，找到和另一个顶点之间的路径，而两种搜索算法，都是解决这个问题的。

2. 广度优先搜索

广度优先搜索的基本思路就是从一个顶点出发，层层遍历，直到找到目标顶点，其实这样搜索出来的路径也就是两个顶点之间的最短距离。如下图所示，例如要搜索出顶点 s -> t 的路径，搜索的方式就是这样的：

其中黄色的线条表示搜索的节点，数字 1、2、3、4 表示搜索的次序，广度优先搜索的原理看起来十分的简单，但是它的代码实现还是稍微有点难的，先来看看整体的代码实现，然后再具体讲解一下：

public class BFS {

    /**
     * 广度优先搜索算法
     * @param graph 图
     * @param s 搜索的起点（对应图中的一个顶点）
     * @param t 搜索的终点
     */
    public static void bfs(Graph graph, int s, int t){
        if (s == t) return;

        //获得图的顶点个数
        int vertex = graph.getVertex();
        //获取存储图顶点的列表
        LinkedList[] list = graph.getList();
        //如果某个顶点已经被访问，则设置为true
        boolean[] visited = new boolean[vertex];
        visited[s] = true;
        //队列，存储的是已经被访问，但是其相连的顶点还没有被访问的顶点
        Queue queue = new LinkedList<>();
        queue.add(s);
        //记录搜索的路径
        int[] path = new int[vertex];
        for (int i = 0; i < vertex; i++) {
            path[i] = -1;
        }

        while (queue.size() != 0){
            int w = queue.poll();
            for (int i = 0; i < list[w].size(); i++) {
                int q = list[w].get(i);
                if (!visited[q]){
                    path[q] = w;
                    if (q == t){
                        print(path, s, t);
                        return;
                    }
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    //递归打印 s-t 的路径
    private static void print(int[] prev, int s, int t){
        if (prev[t] != -1 && t != s){
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
}

程序中有三个辅助的变量：

一是 boolean[] visited ，这个数组表示如果已经被访问，则设置为 true，例如顶点 s，是最开始被访问的，直接设置为 true。

二是有一个队列 queue，它表示的是，一个顶点已经被访问，但是其相邻的顶点还没有被访问的顶点。例如顶点 s，它自己被访问了，但是和它相邻的两个顶点还没有被访问，因此直接被添加到了队列当中。

三是数组 path，它表示一个顶点是被哪个顶点所访问的，数组下标表示的是顶点，对应存储的是由谁所访问。这个逻辑在代码中的体现便是 path[q] = w 这一行。最后，这个数组中存储的便是搜索的路径，需要递归打印出来。

3. 深度优先搜索

再来看看深度优先搜索，这种搜索的基本思路就是：从起始顶点出发，任意遍历顶点，如果走不通，则回退一个顶点，然后换一个顶点继续遍历，知道找到目标顶点。像下图这样：

图中从顶点 s 出发，蓝色的表示前进的顶点，红色的表示后退一个顶点，直到找到目标顶点 t，相信你可以看出来，这样搜索出来的路径其实并不是 s 到 t 的最短路径，而是任意的一条路径。

深度优先的代码实现：

public class DFS {

    //判断是否找到了目标顶点
    private static boolean found =  false;

    public static void dfs(Graph graph, int s, int t){
        int vertex = graph.getVertex();
        boolean[] visited = new boolean[vertex];

        int[] path = new int[vertex];
        for (int i = 0; i < vertex; i++) {
            path[i] = -1;
        }

        LinkedList[] list = graph.getList();
        recursionDfs(list, s, t, visited, path);
        print(path, s, t);
    }

    //递归遍历
    private static void recursionDfs(LinkedList[] list, int w, int t, boolean[] visited, int[] path){
        if (found) return;

        visited[w] = true;
        if (w == t){
            found = true;
            return;
        }

        for (int i = 0; i < list[w].size(); i++) {
            int q = list[w].get(i);
            if (!visited[q]){
                path[q] = w;
                recursionDfs(list, q, t, visited, path);
            }
        }
    }
    private static void print(int[] path, int s, int t){
        if (path[t] != -1 && t != s){
            print(path, s, path[t]);
        }
        System.out.print(t + " ");
    }
}

变量 boolean[] visited 和广度优先搜索一样，都是表示访问过的节点设置为 true，path 数组表示访问的路径。

最后，总结一下，广度和深度优先搜索，都是比较暴力的搜索方式，没有什么优化，层层遍历或者一路递归，所以不难看出，这两个算法的时间复杂度接近 O(n)，空间复杂度也是 O(n)，还是稍微有点高的，所以这两种搜索算法适用于图上的顶点数据不太多的情况。

云服务器 GPU云服务器广度优先搜索算法代码广度优先搜索深度优先搜索最佳优先搜索算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73974.html

学习JavaScript数据结构与算法 — 深度优先搜索算法

摘要：深度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。用深度优先搜索算法对图中的任务图进行拓扑排序最终各顶点的发现和探索完成时间会保存在中。深度优先搜索（DFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中深度优先搜索算法会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点，接着原路回退并探索下一条路径。换句话说，它是先深度后广...

李增田 2019-08-22 11:09 评论0 收藏0
算法-图和图算法

摘要：图的定义用图对现实中的系统建模可以用图对现实中的很多系统建模比如对交通流量建模顶点可以表示街道的十字路口边可以表示街道加权的边可以表示限速或者车道的数量建模人员可以用这个系统来判断最佳路线及最有可能堵车的街道任何运输系统都可以用图来建模比如图的定义用图对现实中的系统建模可以用图对现实中的很多系统建模. 比如对交通流量建模, 顶点可以表示街道的十字路口, 边可以表示街道. 加权的边...

Anshiii 2019-08-23 12:15 评论0 收藏0
深度优先和广度优先--搜索算法

摘要：树状结构张飞关羽刘备荀彧关平点击曹操这一项，加载出来刘禅和周仓，点击周仓，又异步加载项羽和别姬曹操刘禅周仓项羽别姬貂蝉深度优先对于入参的判断，必须存在且是一个数组，如果不是，进行矫正必须是一个字符串，不能是函数之类的必须是一个函数广度优先 1 树状结构 var result = { id:0, name:张飞, item:[ {id:1,name...

molyzzx 2019-08-22 18:16 评论0 收藏0
学习JavaScript数据结构与算法 — 广度优先搜索算法

摘要：广度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。其它最短路径算法对于加权图的最短路径，广度优先算法可能并不合适。广度优先搜索（BFS）上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的...

eternalshallow 2019-08-22 11:09 评论0 收藏0
深度优先搜索和广度优先搜索

摘要：不撞南墙不回头深度优先搜索基础部分对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。这就是深度优先搜索了，当然，这个题目我们还有别的解法，这就到了我们说的广度优先搜索。不撞南墙不回头-深度优先搜索基础部分对于深度优先搜索和广度优先搜索，我很难形象的去表达它的定义。我们从一个例子来切入。输入一个数字n，输出1~n的全排列。即n=3时，输出123，132，213，231，...

huaixiaoz 2019-07-31 10:02 评论0 收藏0