图是一种比较复杂的非线性数据结构。图分很多种，无向图，有向图，带权图，稀疏图等等。本文主要分享了无向图的两种暴力搜索算法BFS(广度优先搜索)和DFS(深度优先搜索)。所有源码均已上传至github:

准备

在这之前，先初始化一个无向图，用LinkedList来当邻接表存储图

private Graph(int count) {        this.count = count;        adj = new LinkedList[count];        for (int i = 0; i < adj.length; i++) {            adj[i] = new LinkedList<>();        }    }复制代码

这里为了插入方便，一条边直接存两次

private void add(int oSide, int rSide) {        adj[oSide].add(rSide);        adj[rSide].add(oSide);    }复制代码

构造一个无向图

private void createGraph() {        //  0 -- 1 -- 2        //  |    |    |        //  3 -- 4 -- 5        //  |    |    |        //  6 -- 7 -- 8        add(0,1);//add(1,0);        add(0,3);//add(3,0);        add(1,2);//add(2,1);        add(1,4);// add(4,1);        add(2,5);//add(5,2);        add(3,4);//add(4,3);        add(3,6);//add(6,3);        add(4,5);//add(5,4);        add(4,7);// add(7,4);        add(5,8);//add(8,5);        add(6,7);//add(7,6);        add(7,8);//add(8,7);    }复制代码

准备完毕

BFS(广度优先搜索)

分析

广度优先搜索，从字面意思理解，它就是一种“地毯式”的搜索策略，先查找离起始顶点最近的，然后是次近的，依次往外搜索，层层递进。

注意

在这里三个重要的核心辅助变量 visited、queue、prev。

• visited 记录已经被访问的顶点，避免顶点被重复访问
• queue 用来存储已经被访问、但相连的顶点还没有被访问的顶点的这样的一个队列。
• prev 记录搜索路径，它是反向存储，便于后续正向打印输出图的路径。

这里看一下它的打印方式就理解prev的存储机制了。

private void print(int[] prev, int oSide, int rSide) {        if (prev[rSide] != -1 && oSide != rSide) {            print(prev, oSide, prev[rSide]);        }        System.out.print(rSide + " ");    }复制代码

解析

首先先将起点oSide加入队列queue，然后在该while循环里，遍历该节点的邻接表，再通过visited进行判断，看是否访问，一直到遍历出的value == rSide 说明已找到，否则让visited 记录该顶点已访问，同时入队，就这样通过不停地入队出队。

ps：遍历出的图的路径也是它的最短路径。

private void bfs(int oSide, int rSide) {        if (oSide == rSide) return;        boolean[] visited = new boolean[count];        visited[oSide] = true;        Queue
     
       queue = new LinkedList<>();        queue.offer(oSide);        int[] prev = new int[count];        for (int i = 0; i < count; i++) {            prev[i] = -1;        }        while (!queue.isEmpty()) {            int index = queue.poll();            for (int j = 0; j < adj[index].size(); j++) {                int value = adj[index].get(j);                if (!visited[value]) {                    prev[value] = index;                    if (value == rSide) {                        print(prev, oSide, rSide);                    }                    visited[value] = true;                    queue.offer(value);                }            }        }    }复制代码
     

DFS(深度优先搜索)

private boolean found = false;   private void dfs(int oSide, int rSide) {        boolean[] visited = new boolean[count];        int[] prev = new int[count];        for (int i = 0; i < count; i++) {            prev[i] = -1;        }        recursiveDfs(visited, prev, oSide, rSide);        print(prev, oSide, rSide);    }    private void recursiveDfs(boolean[] visited, int[] prev, int oSide, int rSide) {        if (found) return;        visited[oSide] = true;        if (oSide == rSide) {            found = true;            return;        }        for (int i = 0; i < adj[oSide].size(); i++) {            int value = adj[oSide].get(i);            if (!visited[value]) {                prev[value] = oSide;                recursiveDfs(visited, prev, value, rSide);            }        }    }复制代码

public static void main(String[] args) {    int count = 9;    Graph graph = new Graph(count);    //  0 -- 1 -- 2    //  |    |    |    //  3 -- 4 -- 5    //  |    |    |    //  6 -- 7 -- 8    graph.createGraph();    System.out.println("BFS(广度优先搜索)");    graph.bfs(0,8);    System.out.println();    System.out.println("DFS(深度优先搜索)");    graph.dfs(0,8);}复制代码