App下載

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

初曉微芒 2023-07-07 13:48:37 瀏覽數(shù) (1827)
反饋

在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),請編寫一個(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面試題考察了面試者對BFS算法思想、圖遍歷和隊(duì)列的理解。掌握BFS的基本原理和實(shí)現(xiàn)方式對于解決與圖相關(guān)的問題具有重要意義。在面試中,清晰地解釋算法思路和實(shí)現(xiàn)過程,展現(xiàn)出自己的編程能力和問題解決能力,將為面試成功奠定基礎(chǔ)。

  學(xué)java,就到java編程獅!








0 人點(diǎn)贊