经典Java面试题解析：深度优先搜索（DFS）

在Java的面试中，深度优先搜索（DFS）是常见的算法思想之一。DFS用于解决图遍历、路径搜索和组合问题等。本文将介绍一道经典的Java面试题——深度优先搜索，并提供详细的解析和解题思路。

题目

给定一个无向图，以及一个起始节点和目标节点，请编写一个函数来判断是否存在从起始节点到目标节点的路径。

示例

假设给定以下无向图和起始节点1和目标节点5：

解析与解题思路

深度优先搜索（DFS）是一种遍历图的算法，通过递归或栈的方式实现。下面是使用DFS解决该问题的具体步骤：

创建一个HashSet来记录已访问的节点，以避免重复访问。
定义一个辅助函数dfs，参数包括当前节点、目标节点和已访问节点的HashSet。
在dfs函数中，首先检查当前节点是否为目标节点，如果是，则返回true。
将当前节点添加到已访问的节点HashSet中。
遍历当前节点的所有相邻节点，对于每个相邻节点，如果它没有被访问过，则递归调用dfs函数。
如果在任何递归调用中找到目标节点，则返回true。
如果所有的递归调用都未找到目标节点，则返回false。

下面是使用DFS解决该问题的Java代码示例：

import java.util.*;

public class GraphDFS {
    private Map<Integer, List<Integer>> graph;

    public GraphDFS() {
        graph = new HashMap<>();
    }

    public void addEdge(int u, int v) {
        graph.computeIfAbsent(u, ArrayList::new).add(v);
        graph.computeIfAbsent(v, ArrayList::new).add(u);
    }

    public boolean hasPath(int start, int target) {
        Set<Integer> visited = new HashSet<>();
        return dfs(start, target, visited);
    }

    private boolean dfs(int curr, int target, Set<Integer> visited) {
        if (curr == target) {
            return true;
        }

        visited.add(curr);
        List<Integer> neighbors = graph.getOrDefault(curr, new ArrayList<>());

        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, target, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        GraphDFS graph = new GraphDFS();
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(4, 5);

        int start = 1;
        int target = 5;
        boolean hasPath = graph.hasPath(start, target);
        System.out.println("Path exists from " + start + " to " + target + ": " + hasPath);
    }
}

在上述代码中，我们通过DFS算法遍历无向图，判断是否存在从起始节点到目标节点的路径。

结论

通过使用深度优先搜索（DFS），我们可以遍历图并判断是否存在从起始节点到目标节点的路径。这道经典的Java面试题考察了面试者对DFS算法思想、图遍历和递归的理解。掌握DFS的基本原理和实现方式对于解决与图相关的问题具有重要意义。在面试中，清晰地解释算法思路和实现过程，展现出自己的编程能力和问题解决能力，将为面试成功奠定基础。

学java，就到java编程狮！