数据结构 图论5 DFS和BFS深度优先搜索和广度优先搜索详解 java

阅读前请先了解邻接矩阵

DFS深度优先搜索

DFS（Deep First Search），递归最深度访问其所有的临近节点（类似二叉树先序遍历);

比如A节点的临近节点就是C，D；C的临近节点就是A，B；

访问临近节点的优先级是A --> B --> C --> D --> E --> F,比如说A有C，D2个临近节点就会先访问C节点；

访问过的节点不再访问（通过visited标记）

例如：下面以A节点为起始点

• 访问A节点，然后按照优先级访问C节点
• C节点的邻近节点A已经visited，访问B节点
• B节点D邻近节点C已经visited，B没有可以访问的节点，回退到A节点（类似二叉树先序遍历);
• A节点向D节点访问
• D节点 的 A，C邻近节点都已经visited，访问E节点
• E节点的D邻近节点已经visited，访问F节点
  
  
  

注意这里访问并没有结束，因为我们还有很多分支没有遍历，优先级 “A --> B --> C --> D --> E --> F”,所以我们按照原路返回。（类似先序遍历）

• 回退到E节点，E节点的所有邻近节点都visited
• 回退到D节点，（检查F节点，不是邻近节点）D节点的所有邻近节点都visited
• 回退到A节点，（检查E，F节点，不是邻近节点）A节点的所有邻近节点都visited

DFS结束 输出的顺序依次是 A --> C --> B --> D --> E --> F （0 - 2 - 1 - 3 - 4 - 5 ）

代码

public class DFS {
    //A, B, C,D, E, F
    static int[][] graph = new int[][]{
            {0, 0, 1, 1, 0, 0},
            {0, 0, 1, 0, 0, 0},
            {1, 1, 0, 0, 0, 0},
            {0, 0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0, 1},
            {0, 0, 0, 0, 1, 0}};
    static int[] visited = new int[graph.length];//用来记录已经遍历过的元素
    //DFS(深度优先遍历)同样适用于有向图 A->C->B->D->E->F 即 0->2->1->3->4->5
    public static void  dfsTraversing(int node, int[][] graph) {
        //遍历输出
        visited[node]=1;
        System.out.println(node);
        //循环一个长度
        for (int i = 0; i < graph[node].length; ++i) {
            //visited = 0；就是这个节点没有visited
            //i != node 就是传入的visited节点不是node，我们需要以node节点的下一个节点为基础，DFS
            //graph[node][i] == 1 保证这个node节点的下一个节点是可以通行的
            if (visited[i]==0&&i != node&&graph[node][i]==1) {
                dfsTraversing(i, graph);
            }
        }
    }

}

BFS 广度优先遍历

广度优先遍历类似树的层序遍历，比如我们将一个图按照起始点为A展开。

先遍历第一层，A；然后遍历第二层 C ，D；然后遍历第三层 B，E，最后遍历第四层 F。

利用队列来实现

每次poll出一个节点就将这个节点没有visited过的邻近点offer推入队列（比如A出队列，C，D就如队列）

入队列Queue的时候输出节点

例如：下面以A为起始节点

• A入队列。输出A （queue={A})
• A出队列 ，A的没有visited的邻近节点 C ，D入队列。输出C，D；（queue={C,D})
• C出队列，C周围没有visited的B节点入队列；D出队列，D周围没有visited的节点E入队列。输出B，E；（queue={B,E})
• B出队列，B周围都已经visited；E出队列E周围没有visited的F入队列。输出F；（queue={F})
• F出队列，B周围都已经visited，且队列里面没有值，循环结束，程序结束

代码

public static void bfs(int[][] graph,int firstNode){
        LinkedList<Integer> queue = new LinkedList<>();
        int length = graph.length;
        System.out.println(firstNode);
        visited[firstNode] = true;
        queue.offer(firstNode);
        while (queue.size() > 0){
            //poll出一个值
            int node = queue.poll();
            //遍历这个行
            for (int i = 0; i < length; i++) {
                //如果行中有可以通行的点i
                //并且这个通行的点i没visited
                if (graph[node][i] != 0 && visited[i] == false) {
                    System.out.println(i);
                    //标记visited
                    visited[i] = true;
                    //就将这个点i入队列
                    queue.offer(i);
                }
            }
        }
    }

总代码

public class DfsAndBfs {
    /**
     * A,B,C,D,E,F
     * 0,1,2,3,4,5
     */
    private int[][] graph;
    /**
     * visited用来记录已经遍历过的元素
     */
    private boolean[] visited;

    public DfsAndBfs(int[][] graph) {
        this.graph = graph;
        visited = new boolean[graph.length];
    }
    /**
     * BFS(广度优先遍历) 基于队列实现
     */
    public  void bfs( int firstNode) {
        LinkedList<Integer> queue = new LinkedList<>();
        int length = graph.length;
        System.out.println(firstNode);
        visited[firstNode] = true;
        queue.offer(firstNode);
        while (queue.size() > 0) {
            //poll出一个值
            int node = queue.poll();
            //遍历这个行
            for (int i = 0; i < length; i++) {
                //如果行中有可以通行的点i
                //并且这个通行的点i没visited
                if (graph[node][i] != 0 && visited[i] == false) {
                    System.out.println(i);
                    //标记visited
                    visited[i] = true;
                    //就将这个点i入队列
                    queue.offer(i);
                }
            }
        }
    }

    /**
     * DFS 深度优先遍历 递归实现
     * （也可通过栈实现，因为递归的本质就是压栈）
     */
    public  void dfs(int node) {
        //遍历输出
        visited[node] = true;
        System.out.println(node);
        //循环一个长度
        for (int i = 0; i < graph[node].length; ++i) {
            //visited = false；就是这个节点没有visited
            //i != node 就是传入的visited节点不是node，我们需要以node节点的下一个节点为基础，DFS
            //graph[node][i] == 1 保证这个node节点的下一个节点是可以通行的
            if (visited[i] == false && i != node && graph[node][i] == 1) {
                dfs(i);
            }
        }
    }

}

test

int[][] graph = new int[][]{
  {0, 0, 1, 1, 0, 0},
  {0, 0, 1, 0, 0, 0},
  {1, 1, 0, 0, 0, 0},
  {0, 0, 1, 0, 1, 0},
  {0, 0, 0, 1, 0, 1},
  {0, 0, 0, 0, 1, 0}};

//0 2 1 3 4 5
new DfsAndBfs(graph).dfs(0);
System.out.println("==========");
//因为遍历会改变visited的值，所以需要重新构造对象
//0 2 3 1 4 5
new DfsAndBfs(graph).bfs(0);

refrence：

图的搜索算法：BFS和DFS详解（Java实现） - 简书 (jianshu.com)