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

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

题目

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

示例

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

     1 -- 2
    / 
   3 - 4
        
         5

解析与解题思路

广度优先搜索（BFS）是一种遍历图的算法，通过队列实现。下面是使用 BFS 解决该问题的具体步骤：

1. 创建一个队列（通常使用 LinkedList 实现）来存储待遍历的节点。
2. 创建一个 HashSet 来记录已访问的节点，以避免重复访问。
3. 将起始节点放入队列，并将其标记为已访问。
4. 在循环中，从队列中取出一个节点，并检查其是否为目标节点。如果是，则存在从起始节点到目标节点的路径，返回 true。
5. 如果当前节点不是目标节点，将其未访问的相邻节点放入队列，并标记为已访问。
6. 重复步骤 4 和 5，直到队列为空。
7. 如果队列为空且未找到目标节点，则不存在从起始节点到目标节点的路径，返回 false。

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

import java.util.*;

public class GraphBFS {private Map> graph;

    public GraphBFS() {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) {Queue queue = new LinkedList();
        Set visited = new HashSet();

        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {int curr = queue.poll();

            if (curr == target) {return true;}

            List neighbors = graph.getOrDefault(curr, new ArrayList());

            for (int neighbor : neighbors) {if (!visited.contains(neighbor)) {queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {GraphBFS graph = new GraphBFS();
        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);
    }
}

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

结论

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

  学 java，就到 java 编程狮 ！