Java深度优先搜索DFS(含面试大厂题和源码)

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。DFS 通过沿着树的深度来遍历节点，尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复上述过程，整个过程重复进行，直到所有节点都被访问为止。

深度优先搜索的实现方式：

递归实现：使用递归函数实现DFS，每次递归调用都访问一个未被访问的相邻节点。
非递归实现（栈）：使用栈来模拟递归过程，每次从栈中取出一个节点，访问其未被访问的相邻节点，并将其压入栈中。

深度优先搜索的应用：

解决迷宫问题：DFS 可以用来找到迷宫的解，通过不断尝试不同的路径直到找到出口。
拓扑排序：在有向无环图（DAG）中，DFS 可以用来进行拓扑排序。
寻找连通分量：在无向图中，DFS 可以用来找到连通分量。
路径查找：在图论中，DFS 可以用来寻找两个节点之间的路径。

深度优先搜索的Java实现（栈）：

import java.util.*;public class DepthFirstSearch {private Map<Integer, List<Integer>> graph;private boolean[] visited;public DepthFirstSearch(Map<Integer, List<Integer>> graph) {this.graph = graph;this.visited = new boolean[graph.size()];}public void dfs(int start) {Stack<Integer> stack = new Stack<>();stack.push(start);visited[start] = true;while (!stack.isEmpty()) {int node = stack.pop();System.out.print(node + " ");for (int neighbor : graph.get(node)) {if (!visited[neighbor]) {visited[neighbor] = true;stack.push(neighbor);}}}}public static void main(String[] args) {Map<Integer, List<Integer>> graph = new HashMap<>();graph.put(0, Arrays.asList(1, 2));graph.put(1, Arrays.asList(3));graph.put(2, Arrays.asList(3));graph.put(3, Collections.emptyList());graph.put(4, Arrays.asList(5));graph.put(5, Collections.emptyList());DepthFirstSearch dfs = new DepthFirstSearch(graph);dfs.dfs(0); // 应输出 0 1 3 2}
}

在面试中，深度优先搜索是一个重要的算法问题，它考察应聘者对图的遍历和递归的理解。通过实现深度优先搜索，可以展示你对基本算法和数据结构的掌握程度。希望这些知识点和示例代码能够帮助你更好地准备面试！

题目 1：二叉树的深度

描述：
给定一个二叉树，找出其最大深度。

示例：

输入: 二叉树3/ \9  20/   \15   7
输出: 3

Java 源码：

public class MaxDepth {public int maxDepth(TreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}public static void main(String[] args) {MaxDepth solution = new MaxDepth();TreeNode root = new TreeNode(3);root.left = new TreeNode(9);root.right = new TreeNode(20);root.left.right = new TreeNode(15);root.right.left = new TreeNode(7);int result = solution.maxDepth(root);System.out.println("Max depth of binary tree: " + result);}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

题目 2：路径总和

描述：
给定一个二叉树和一个目标和，确定所有从根到叶子的路径上总和等于目标和的路径。

示例：

输入: 二叉树，sum = 255/ \4   8/   / \11  13  4/  \      \7    2      9
输出: [[5,4,11,7], [5,8,4,4]]

Java 源码：

public class PathSum {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();dfs(root, sum, path, result);return result;}private void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> result) {if (node == null) {return;}path.add(node.val);if (node.left == null && node.right == null && remaining == node.val) {result.add(new ArrayList<>(path));}dfs(node.left, remaining - node.val, path, result);dfs(node.right, remaining - node.val, path, result);path.remove(path.size() - 1);}public static void main(String[] args) {PathSum solution = new PathSum();TreeNode root = new TreeNode(5);root.left = new TreeNode(4);root.right = new TreeNode(8);root.left.left = new TreeNode(11);root.left.right = new TreeNode(13);root.right.left = new TreeNode(4);root.right.right = new TreeNode(7);root.left.right.left = new TreeNode(2);root.left.right.right = new TreeNode(9);List<List<Integer>> result = solution.pathSum(root, 25);System.out.println("Path sum: " + result);}
}

题目 3：子图同构

描述：
给定两个有向图，判断它们是否是同构的。如果一个图的节点可以一一映射到另一个图的节点，并且映射后的图与原图结构相同，则这两个图是同构的。

示例：

输入: 两个图的邻接表表示
图1: [[1,2],[2,3],[3,4]]
图2: [[1,2],[2,3],[3,4]]
输出: true

Java 源码：

public class GraphIsomorphism {public boolean isIsomorphic(Map<Integer, List<Integer>> graph1, Map<Integer, List<Integer>> graph2) {if (graph1.size() != graph2.size()) {return false;}Map<Integer, Integer> mapping = new HashMap<>();Queue<Integer> queue = new LinkedList<>();queue.offer(1);mapping.put(1, 1);while (!queue.isEmpty()) {int node1 = queue.poll();int node2 = mapping.get(node1);List<Integer> neighbors1 = graph1.get(node1);List<Integer> neighbors2 = graph2.get(node2);if (!neighbors1.size() == neighbors2.size()) {return false;}for (int i = 0; i < neighbors1.size(); i++) {int neighbor1 = neighbors1.get(i);int neighbor2 = neighbors2.get(i);if (!mapping.containsKey(neighbor1)) {queue.offer(neighbor1);mapping.put(neighbor1, neighbor2);} else if (!mapping.get(neighbor1).equals(neighbor2)) {return false;}}}return true;}public static void main(String[] args) {GraphIsomorphism solution = new GraphIsomorphism();Map<Integer, List<Integer>> graph1 = new HashMap<>();graph1.put(1, Arrays.asList(2));graph1.put(2, Arrays.asList(3));graph1.put(3, Arrays.asList(4));Map<Integer, List<Integer>> graph2 = new HashMap<>();graph2.put(1, Arrays.asList(2));graph2.put(2, Arrays.asList(3));graph2.put(3, Arrays.asList(4));boolean result = solution.isIsomorphic(graph1, graph2);System.out.println("Graphs are isomorphic: " + result);}
}