Java深度优先搜索（DFS）算法实现

贺公子之数据科学与艺术

发布于 2025-08-29 17:52:15

13300

代码可运行

运行总次数：0

代码可运行

标题：Java深度优先搜索（DFS）算法实现

引言：

深度优先搜索（Depth-First Search，DFS）是一种常用的图遍历算法，它通过递归地遍历图中的每个顶点，来寻找特定的路径或解决某些问题。本篇博客将介绍如何用Java语言实现深度优先搜索算法。

算法思想：

深度优先搜索算法的基本思想是先访问一个顶点，然后递归地访问此顶点的相邻顶点，直到达到某个终点或无法继续递归。如果还存在未被访问的顶点，则选择一个未被访问的顶点继续递归。整个过程可以看作是一种“探索”的过程，类似于在迷宫中寻找出口的过程。

算法实现：

下面是用Java语言实现深度优先搜索算法的伪代码：

class DepthFirstSearch {
    private boolean[] visited;  // 标记顶点是否已被访问
    private Graph graph;  // 图的邻接表表示方式
    
    public DepthFirstSearch(Graph graph) {
        this.graph = graph;
        visited = new boolean[graph.V()];
    }

    // 深度优先搜索算法
    public void dfs(int v) {
        visited[v] = true;  // 标记顶点v已被访问
        System.out.print(v + " ");  // 输出顶点v
        
        // 递归访问v的邻接顶点
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
    }
}

在上述代码中，我们使用了一个布尔数组visited来标记顶点是否已被访问。在深度优先搜索算法中，我们首先将起始顶点标记为已访问，并将其输出。然后递归地访问该顶点的邻接顶点（即未被访问的相邻顶点），直到没有未被访问的邻接顶点为止。

应用案例：

下面是一个示例应用，展示了如何使用深度优先搜索算法来遍历图中的所有顶点：

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);  // 创建一个含有5个顶点的图
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        DepthFirstSearch dfs = new DepthFirstSearch(graph);
        dfs.dfs(0);  // 从顶点0开始深度优先搜索
    }
}

上述示例中，我们首先创建了一个含有5个顶点的图，并添加了一些边。然后，我们创建了一个DepthFirstSearch对象，并使用dfs方法从顶点0开始深度优先搜索。最终，输出的结果将是遍历的顶点序列。