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

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

題目

給定一個(gè)無向圖，以及一個(gè)起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，請(qǐng)編寫一個(gè)函數(shù)來判斷是否存在從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑。

示例

假設(shè)給定以下無向圖和起始節(jié)點(diǎn)1和目標(biāo)節(jié)點(diǎn)5：

     1 -- 2
    / \
   3 - 4
        \
         5

解析與解題思路

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

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

結(jié)論

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

  學(xué)java，就到java編程獅！