App下載

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

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

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

題目

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

示例

假設(shè)給定以下無向圖和起始節(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é)點的路徑。

結(jié)論

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

  學java，就到java編程獅！


Java

0 人點贊