Java实现深度优先搜索(DFS)和广度优先搜索(BFS)算法

Java实现深度优先搜索(DFS)和广度优先搜索(BFS)算法

深度优先搜索(DFS)和广度优先搜索(BFS)算法是常用的遍历和搜索算法，具有很高的实用价值。在Java中，我们可以通过使用递归函数和队列这两种数据结构来实现这两种算法。下面将对这两种算法进行详细的讲解。

深度优先搜索(DFS)

深度优先搜索(DFS)是一种常用的遍历算法，其思想就是从起点开始，先遍历尽可能深的节点，直到不能再遍历为止，然后回溯到上一个未遍历的节点。在实现中，我们可以使用递归函数来实现DFS算法。

public class DFS {

    public static void dfs(int[][] graph, int start, boolean[] visited) {

        visited[start] = true;  //将当前节点标记为已访问

        System.out.print(start + " "); //输出当前节点

        for (int i = 0; i < graph.length; i++) {
            if (graph[start][i] == 1 && !visited[i]) {  //如果当前节点与下一个节点有相邻关系并且下一个节点未被访问过
                dfs(graph, i, visited); //递归访问下一个节点
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 0, 0, 0},
                {1, 0, 0, 1, 1, 0},
                {1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 1, 0},
                {0, 1, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0}
        };

        boolean[] visited = new boolean[graph.length];
        Arrays.fill(visited, false);

        dfs(graph, 0, visited);
    }
}

以上代码中，我使用邻接矩阵来表示图，其中的dfs方法用于递归遍历节点，visited数组用于记录节点是否已经被访问过。

示例1：通过上述代码遍历如下图所示的图

    0 -- 1 -- 3
    |    |    |
    2    4    5

输出结果：0 1 3 4 5 2

广度优先搜索(BFS)

广度优先搜索(BFS)是一种常用的遍历算法，其思想是从起点开始，先遍历所有的相邻节点，然后再遍历相邻节点的相邻节点，直到遍历完所有的节点。在实现中，我们可以使用队列这种数据结构来实现BFS算法。

import java.util.*;

public class BFS {

    public static void bfs(int[][] graph, int start, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();

        visited[start] = true; //将当前节点标记为已访问
        queue.offer(start); //将当前节点加入队列

        while (!queue.isEmpty()) { //只要队列中还有节点
            int node = queue.poll(); //弹出队列中的节点
            System.out.print(node + " "); //输出当前节点

            for (int i = 0; i < graph.length; i++) {
                if (graph[node][i] == 1 && !visited[i]) { //如果当前节点与下一个节点有相邻关系并且下一个节点未被访问过
                    visited[i] = true; //将下一个节点标记为已访问
                    queue.offer(i); //将下一个节点加入队列
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 0, 0, 0},
                {1, 0, 0, 1, 1, 0},
                {1, 0, 0, 0, 0, 1},
                {0, 1, 0, 0, 1, 0},
                {0, 1, 0, 1, 0, 0},
                {0, 0, 1, 0, 0, 0}
        };

        boolean[] visited = new boolean[graph.length];
        Arrays.fill(visited, false);

        bfs(graph, 0, visited);
    }
}

以上代码中，我使用邻接矩阵来表示图，其中的bfs方法用于遍历节点，visited数组用于记录节点是否已经被访问过。

示例2：通过上述代码遍历如下图所示的图

    0 -- 1 -- 3
    |    |    |
    2    4    5

输出结果：0 1 2 3 4 5

通过上述两个示例，我们可以看到DFS和BFS算法具有不同的遍历方式，在不同的问题中，我们可以根据具体情况选择正确的遍历算法。