Java搜索与图论之DFS和BFS算法详解

DFS算法基本原理

DFS(深度优先搜索)指的是从图的某个顶点出发，访问其所有能到达的顶点，并且尽可能深的搜索其中一支支路径的搜索算法。遍历过的点存放到形成的树中。树中每个结点的祖先结点都位于它的所有子树中，它的祖先结点包括它父亲结点和它父亲的祖先结点。DFS一般采用递归或者栈实现，其算法流程如下：

1. 访问起始顶点
2. 标记该顶点以表示已访问
3. 遍历该顶点相邻的所有未访问顶点并递归访问
4. 如果没有未访问顶点，则回退以访问剩余未访问顶点

DFS算法Java代码实现

public static void dfs(int[][] graph, boolean[] visited, int n, int i) {
    visited[i] = true;
    System.out.print(i + " ");
    for (int j = 0; j < n; j++) {
        if (!visited[j] && graph[i][j] == 1) {
            dfs(graph, visited, n, j);
        }
    }
}

其中，graph是图的邻接矩阵，visited是标记数组，n是图中顶点数量，i是遍历的起始顶点。

BFS算法基本原理

BFS(广度优先搜索)指的是先访问已知起始顶点的直接相邻顶点，再依次访问这些相邻顶点的相邻顶点，并标记为已访问。采用队列的方式实现，算法流程如下：

1. 创建一个队列并存储起始顶点
2. 标记起始顶点为已访问
3. 从队列中获取下一个顶点，访问所有未被访问顶点并标记为已访问
4. 把这些未被访问的顶点加入队列中
5. 重复步骤3和4直到队列为空

BFS算法Java代码实现

public static void bfs(int[][] graph, boolean[] visited, int n, int i) {
    visited[i] = true;
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(i);
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        System.out.print(curr + " ");
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[curr][j] == 1) {
                visited[j] = true;
                queue.offer(j);
            }
        }
    }
}

其中，graph是图的邻接矩阵，visited是标记数组，n是图中顶点数量，i是遍历的起始顶点。

示例说明1

以如下二维数组表示的图为例：

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

其中，每行表示一个顶点和其他顶点的连边情况，1表示连通，0表示不连通。

如果起始顶点为2，使用DFS算法，遍历整张图，会输出如下序列：

2 0 1 3 4

如果起始顶点为2，使用BFS算法，遍历整张图，会输出如下序列：

2 0 1 4 3

示例说明2

以如下二维数组表示的图为例：

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

其中，每行表示一个顶点和其他顶点的连边情况，1表示连通，0表示不连通。

如果起始顶点为0，使用DFS算法，遍历整张图，会输出如下序列：

0 1 2 3 4

如果起始顶点为0，使用BFS算法，遍历整张图，会输出如下序列：

0 1 3 2 4