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

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

深度优先搜索（DFS）

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

DFS的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实现：

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。

源码：

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的最短路径。

源码：

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），实现一个算法来执行拓扑排序。

源码：

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);
    }
}

这些题目不仅考察了候选人对DFS和BFS的理解，还考察了他们对图算法的掌握程度。在面试中，清晰地表达你的思考过程和代码逻辑是非常重要的。