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

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

题目

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

示例

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

     1 -- 2
    / 
   3 - 4
        
         5

解析与解题思路

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

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

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

import java.util.*;

public class GraphDFS {private Map> 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 visited = new HashSet();
        return dfs(start, target, visited);
    }

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

        visited.add(curr);
        List 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 编程狮 ！