經(jīng)典Java面試題解析：廣度優(yōu)先搜索（BFS）

在Java的面試中，廣度優(yōu)先搜索（BFS）是常見的算法思想之一。BFS用于解決圖遍歷、最短路徑和狀態(tài)轉(zhuǎn)換等問題。本文將介紹一道經(jīng)典的Java面試題——廣度優(yōu)先搜索，并提供詳細的解析和解題思路。

題目

給定一個無向圖，以及一個起始節(jié)點和目標節(jié)點，請編寫一個函數(shù)來判斷是否存在從起始節(jié)點到目標節(jié)點的路徑。

示例

假設給定以下無向圖和起始節(jié)點1和目標節(jié)點5：

     1 -- 2
    / \
   3 - 4
        \
         5

解析與解題思路

廣度優(yōu)先搜索（BFS）是一種遍歷圖的算法，通過隊列實現(xiàn)。下面是使用BFS解決該問題的具體步驟：

1. 創(chuàng)建一個隊列（通常使用LinkedList實現(xiàn)）來存儲待遍歷的節(jié)點。
2. 創(chuàng)建一個HashSet來記錄已訪問的節(jié)點，以避免重復訪問。
3. 將起始節(jié)點放入隊列，并將其標記為已訪問。
4. 在循環(huán)中，從隊列中取出一個節(jié)點，并檢查其是否為目標節(jié)點。如果是，則存在從起始節(jié)點到目標節(jié)點的路徑，返回true。
5. 如果當前節(jié)點不是目標節(jié)點，將其未訪問的相鄰節(jié)點放入隊列，并標記為已訪問。
6. 重復步驟4和5，直到隊列為空。
7. 如果隊列為空且未找到目標節(jié)點，則不存在從起始節(jié)點到目標節(jié)點的路徑，返回false。

下面是使用BFS解決該問題的Java代碼示例：

import java.util.*;

public class GraphBFS {
    private Map<Integer, List<Integer>> 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<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

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

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

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

            List<Integer> 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算法遍歷無向圖，判斷是否存在從起始節(jié)點到目標節(jié)點的路徑。

結(jié)論

通過使用廣度優(yōu)先搜索（BFS），我們可以遍歷圖并判斷是否存在從起始節(jié)點到目標節(jié)點的路徑。這道經(jīng)典的Java面試題考察了面試者對BFS算法思想、圖遍歷和隊列的理解。掌握BFS的基本原理和實現(xiàn)方式對于解決與圖相關的問題具有重要意義。在面試中，清晰地解釋算法思路和實現(xiàn)過程，展現(xiàn)出自己的編程能力和問題解決能力，將為面試成功奠定基礎。

  學java，就到java編程獅！