深度优先和广度优先搜索算法 DFS BFS

一、深度优先搜索 DFS

概述

深度优先搜索（Depth First Search，DFS）是一种用于遍历图或树数据结构的递归算法。该算法从根节点开始，尽可能深地探索每个分支，直到无法继续前进为止，然后回溯到上一个节点，继续探索其他分支。为了避免重复访问节点，需要使用额外的内存（通常是一个栈）来跟踪已经发现的节点。

深度优先搜索的时间复杂度为O(V + E)，其中V是节点数，E是边数。空间复杂度为O(V)。

深度优先搜索在许多领域有广泛的应用，例如寻找路径、检测图是否为二分图、寻找强连通分量和检测图中的环等。

dfs.gif

实现思路

深度优先搜索的实现可以使用递归或非递归方式。递归实现是最直观的方式，但可能在处理大型图时导致栈溢出。非递归实现使用一个栈来模拟递归过程，可以处理更大规模的图。

非递归实现步骤

1. 将任意一个节点作为起始节点，并将其标记为已访问。
2. 将起始节点的所有未访问邻居节点加入栈中。
3. 从栈中取出栈顶节点，并将其标记为已访问。
4. 将该节点的所有未访问邻居节点加入栈中。
5. 重复步骤3和步骤4，直到栈为空。

下面是深度优先搜索的伪代码实现：

procedure DFS(G, v) is
    label v as discovered
    for each edge (v, w) in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

二、广度优先搜索 BFS

概述

广度优先搜索（Breadth First Search，BFS）是一种用于遍历图或树数据结构的算法。该算法从根节点开始，逐层地遍历节点，先访问当前层的所有节点，然后再访问下一层的节点。在搜索过程中，使用一个队列来存储待访问的节点，并使用一个标记数组来记录已经访问过的节点，以避免重复访问。

广度优先搜索的时间复杂度为O(V + E)，其中V是节点数，E是边数。空间复杂度为O(V)。

广度优先搜索在许多领域有广泛的应用，例如寻找最短路径、检测图是否连通、生成迷宫的最短路径等。

bfs.gif

实现思路

广度优先搜索的实现可以使用队列来模拟搜索过程。通过不断将邻居节点加入队列，并按照先进先出的顺序访问节点，可以确保按层级遍历图或树。

实现步骤

1. 将起始节点放入队列中，并标记为已访问。
2. 从队列中取出一个节点，并访问该节点。
3. 将该节点的所有未访问邻居节点加入队列，并标记为已访问。
4. 重复步骤2和步骤3，直到队列为空。

下面是广度优先搜索的伪代码实现：

procedure BFS(G, start) is
    let Q be a queue
    Q.enqueue(start)
    mark start as visited
    while Q is not empty do
        v := Q.dequeue()
        process v
        for each neighbor w of v do
            if w is not visited then
                Q.enqueue(w)
                mark w as visited

三、Java代码示例

实现思路:
用数组表示顶点, 数组元素为LinkedList<Integer>表示边. 例如,
adjList[0]有列表[1, 3, 5] --代表顶点0有三条边, 分别连接顶点1, 3, 5

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class DfsAndBfs {

    // adjLists表示顶点集合,每个顶点都有List.size()条边
    private final LinkedList<Integer>[] adjLists;
    // 表示第i个顶点是否访问过
    private final boolean[] visited;

    /**
     * 指定有几个节点
     * @param vertices 节点数
     */
    DfsAndBfs(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList<>();
    }

    /**
     * 输入起点和终点, 构造定点的边
     * @param src 起点
     * @param dest 终点
     */
    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    /**
     * 深度优先搜索, 递归实现
     * @param start 起始节点
     */
    void DFS(int start) {
        visited[start] = true;
        System.out.print(start);
        for (int adj : adjLists[start]) {
            if (!visited[adj]) {
                System.out.print(" -> ");
                DFS(adj);
            }
        }
    }

    /**
     * 深度优先搜索, 非递归实现
     * @param start 起始节点
     */
    void DFS_notRecursion(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        visited[start] = true;
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            System.out.print(vertex);

            // 将其子元素从右往左循环入栈
            for (int i = adjLists[vertex].size() - 1; i >= 0; i--) {
                Integer eachTarget = adjLists[vertex].get(i);
                if (!visited[eachTarget]) {
                    visited[eachTarget] = true;
                    stack.push(eachTarget);
                }
            }
            if (!stack.isEmpty()) {
                System.out.print(" -> ");
            }
        }
    }

    /**
     * 广度优先搜索
     * @param start 起始节点
     */
    void BFS(int start) {
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            // 取出头部元素,将其子元素加入到队列尾部
            int vertex = queue.poll();
            System.out.print(vertex);
            for (int adj : adjLists[vertex]) {
                if (!visited[adj]) {
                    visited[adj] = true;
                    queue.add(adj);
                }
            }
            if (!queue.isEmpty()) {
                System.out.print(" -> ");
            }
        }
    }

    public static void main(String[] args) {
        testDfs();
        testDFS_notRecursion();
        testBfs();
    }

    private static void testDfs() {
        DfsAndBfs g = new DfsAndBfs(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        System.out.print("Depth First Traversal: ");
        g.DFS(0);
        System.out.println();
    }

    private static void testDFS_notRecursion() {
        DfsAndBfs g = new DfsAndBfs(6);
        g.addEdge(0, 1);
        g.addEdge(0, 3);
        g.addEdge(0, 5);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(1, 5);
        System.out.print("Depth First Traversal Not Recursion: ");
        g.DFS_notRecursion(0);
        System.out.println();
    }

    private static void testBfs() {
        DfsAndBfs g = new DfsAndBfs(6);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(2, 4);
        g.addEdge(2, 5);
        System.out.print("Breadth First Traversal: ");
        g.BFS(0);
        System.out.println();
    }
}