App下載

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

廢話輸出機器 2023-07-07 11:49:12 瀏覽數(shù) (2136)
反饋

在Java的面試中,深度優(yōu)先搜索(DFS)是常見的算法思想之一。DFS用于解決圖遍歷、路徑搜索和組合問題等。本文將介紹一道經(jīng)典的Java面試題——深度優(yōu)先搜索,并提供詳細的解析和解題思路。

題目

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

示例

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

     1 -- 2
    / \
   3 - 4
        \
         5

解析與解題思路

 深度優(yōu)先搜索(DFS)是一種遍歷圖的算法,通過遞歸或棧的方式實現(xiàn)。下面是使用DFS解決該問題的具體步驟:

  1. 創(chuàng)建一個HashSet來記錄已訪問的節(jié)點,以避免重復訪問。
  2. 定義一個輔助函數(shù)dfs,參數(shù)包括當前節(jié)點、目標節(jié)點和已訪問節(jié)點的HashSet。
  3. 在dfs函數(shù)中,首先檢查當前節(jié)點是否為目標節(jié)點,如果是,則返回true。
  4. 將當前節(jié)點添加到已訪問的節(jié)點HashSet中。
  5. 遍歷當前節(jié)點的所有相鄰節(jié)點,對于每個相鄰節(jié)點,如果它沒有被訪問過,則遞歸調(diào)用dfs函數(shù)。
  6. 如果在任何遞歸調(diào)用中找到目標節(jié)點,則返回true。
  7. 如果所有的遞歸調(diào)用都未找到目標節(jié)點,則返回false。

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

import java.util.*;

public class GraphDFS {
    private Map<Integer, List<Integer>> graph;

    public GraphDFS() {
        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) {
        Set<Integer> visited = new HashSet<>();
        return dfs(start, target, visited);
    }

    private boolean dfs(int curr, int target, Set<Integer> visited) {
        if (curr == target) {
            return true;
        }

        visited.add(curr);
        List<Integer> neighbors = graph.getOrDefault(curr, new ArrayList<>());

        for (int neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, target, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

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

在上述代碼中,我們通過DFS算法遍歷無向圖,判斷是否存在從起始節(jié)點到目標節(jié)點的路徑。

結論

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

  學java,就到java編程獅


0 人點贊