欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-13 09:39:31
...

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<Integer>[] list = graph.getList();
        //如果某个顶点已经被访问,则设置为true
        boolean[] visited = new boolean[vertex];
        visited[s] = true;
        //队列,存储的是已经被访问,但是其相连的顶点还没有被访问的顶点
        Queue<Integer> 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<Integer>[] list = graph.getList();
        recursionDfs(list, s, t, visited, path);
        print(path, s, t);
    }

    //递归遍历
    private static void recursionDfs(LinkedList<Integer>[] 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),还是稍微有点高的,所以这两种搜索算法适用于图上的顶点数据不太多的情况。