Java深度优先搜索与广度优先搜索知识点（含面试大厂题和源码）

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）是两种常用的图遍历算法，它们在解决图和树结构的问题中非常有用，如路径搜索、最短路径、网络爬虫、社交网络分析等。

深度优先搜索（DFS）

深度优先搜索从图中的某个顶点开始，尽可能深地搜索图的分支。它沿着树的深度遍历树的节点，同一个层级的节点按从左到右的顺序依次访问。

DFS的Java实现：

java">import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class DFS {public List<List<Integer>> solution(int[][] graph) {List<List<Integer>> results = new ArrayList<>();int[] visited = new int[graph.length];for (int i = 0; i < graph.length; i++) {if (visited[i] == 0) {dfs(graph, i, visited, new ArrayList<>(), results);}}return results;}private void dfs(int[][] graph, int at, int[] visited, List<Integer> path, List<List<Integer>> results) {visited[at] = 1;path.add(at);for (int next : graph[at]) {if (visited[next] == 0) {dfs(graph, next, visited, path, results);}}results.add(new ArrayList<>(path));path.remove(path.size() - 1);}public static void main(String[] args) {int[][] graph = {{1, 2},{0}, // 1的邻接点{1, 3, 4},{2}, // 3的邻接点{1, 4, 5},{1, 2, 3, 4}  // 5的邻接点};DFS dfs = new DFS();List<List<Integer>> results = dfs.solution(graph);for (List<Integer> result : results) {System.out.println(result);}}
}

广度优先搜索（BFS）

广度优先搜索从图中的某个顶点开始，逐层遍历图中的节点，即先访问起始节点的所有邻接点，再访问邻接点的邻接点，依此类推。

BFS的Java实现：

java">import java.util.*;public class BFS {public List<List<Integer>> solution(int[][] graph) {List<List<Integer>> results = new ArrayList<>();int[] visited = new int[graph.length];Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < graph.length; i++) {if (visited[i] == 0) {queue.offer(i);visited[i] = 1;List<Integer> path = new ArrayList<>();while (!queue.isEmpty()) {int at = queue.poll();path.add(at);for (int next : graph[at]) {if (visited[next] == 0) {queue.offer(next);visited[next] = 1;}}}results.add(path);}}return results;}public static void main(String[] args) {int[][] graph = {{1, 2},{0}, // 1的邻接点{1, 3, 4},{2}, // 3的邻接点{1, 4, 5},{1, 2, 3, 4}  // 5的邻接点};BFS bfs = new BFS();List<List<Integer>> results = bfs.solution(graph);for (List<Integer> result : results) {System.out.println(result);}}
}

在实际应用中，DFS和BFS的选择取决于问题的特性。例如，如果需要找到从源点到目标的最短路径，BFS通常是更好的选择，因为它能更快地找到最短路径。而DFS则更适用于寻找所有可能的路径或在深度较深的搜索中。在准备大厂面试时，理解并掌握深度优先搜索（DFS）和广度优先搜索（BFS）是非常重要的。以下是三道与DFS和BFS相关的面试题目，以及它们的Java源码示例。

1. 判断二叉树是否平衡

题目：给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树的定义是：对于树中的任意一个节点，其两个子树的高度差不超过1。

源码：

java">class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}public int height;
}public class IsBalanced {public boolean isBalanced(TreeNode root) {return dfs(root) != -1;}private int dfs(TreeNode node) {if (node == null) {return 0;}int leftHeight = dfs(node.left);if (leftHeight == -1) {return -1;}int rightHeight = dfs(node.right);if (rightHeight == -1) {return -1;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;}return Math.max(leftHeight, rightHeight) + 1;}public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);IsBalanced isBalanced = new IsBalanced();System.out.println(isBalanced.isBalanced(root) ? "Balanced" : "Not Balanced");}
}

2. 最短路径问题

题目：给定一个加权图中的顶点v，找到从源点到顶点v的最短路径。

源码：

java">import java.util.*;public class ShortestPath {public int shortestPath(int[][] graph, int src, int dest) {int V = graph.length;int[] dist = new int[V];Arrays.fill(dist, Integer.MAX_VALUE);dist[src] = 0;boolean[] sptSet = new boolean[V];for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, sptSet);sptSet[u] = true;for (int v = 0; v < V; v++)if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])dist[v] = dist[u] + graph[u][v];}return dist[dest];}private int minDistance(int[] dist, boolean[] sptSet) {int min = Integer.MAX_VALUE, min_index;for (int v = 0; v < dist.length; v++)if (sptSet[v] == false && dist[v] <= min) {min = dist[v], min_index = v;}return min_index;}public static void main(String[] args) {int[][] graph = {{0, 4, 0, 0, 0, 0},{4, 0, 8, 0, 0, 0},{0, 8, 0, 2, 0, 0},{0, 0, 2, 0, 1, 0},{0, 0, 0, 1, 0, 7},{0, 0, 0, 0, 7, 0}};ShortestPath shortestPath = new ShortestPath();int src = 0, dest = 4;System.out.println("最短路径的长度是: " + shortestPath.shortestPath(graph, src, dest));}
}

3. 拓扑排序

题目：给定一个有向无环图（DAG），实现一个算法来执行拓扑排序。

源码：

java">import java.util.*;public class TopologicalSort {public List<Integer> topologicalSort(int V, int[][] graph) {List<Integer> result = new ArrayList<>();int[] indegree = new int[V];Queue<Integer> queue = new LinkedList<>();// 初始化队列和入度数组for (int[] edge : graph) {indegree[edge[1]]++;}for (int i = 0; i < V; i++) {if (indegree[i] == 0) {queue.offer(i);}}// 执行拓扑排序while (!queue.isEmpty()) {int node = queue.poll();result.add(node);for (int[] edge : graph) {if (edge[0] == node) {indegree[edge[1]]--;if (indegree[edge[1]] == 0) {queue.offer(edge[1]);}}}}if (result.size() != V) {throw new IllegalStateException("图有环");}return result;}public static void main(String[] args) {int V = 6;int[][] graph = {{5, 2},{5, 0},{4, 0},{4, 1},{2, 3},{3, 1}};TopologicalSort topologicalSort = new TopologicalSort();List<Integer> result = topologicalSort.topologicalSort(V, graph);System.out.println("拓扑排序结果: " + result);}
}