破題

這道題目要求我們判斷是否存在從起點到終點的有效路徑。這可以轉化為求圖中兩個頂點是否連通的問題。我們可以使用廣度優先搜尋 (BFS)、深度優先搜尋 (DFS)或 Disjoint Set Union (DSU) 來解決這個問題。這些方法都可以幫助我們快速地找到兩個頂點之間是否存在一條有效路徑。

來，一起準備面試吧！
讓我們一起寫一份超級吸睛的履歷吧！從技術主管的視角，幫助你用精練語句量化成效，讓你的履歷表變得更加出色。別再猶豫了，動動手指投遞履歷吧！
立即加入 Line 讀書會，一起準備面試吧！

履歷諮詢	加入讀書會 (邀請碼：2573)

廣度優先搜尋 (BFS)

解題思路

我們要用廣度優先搜尋 (BFS) 來判斷從起點到終點是否有有效的路徑。具體的步驟如下：

• 宣告一個 queue ，用來存儲當前訪問過的節點。
• 宣告一個 boolean 陣列，用來記錄每個節點是否已經訪問過。
• 把起點加入 queue，並標記為已訪問。
• 當 queue 不為空時，重複以下操作：
  • 從 queue 中取出一個頂點，如果它是終點，則回傳 true。
  • 否則，把它的所有未訪問過的相鄰節點加入 queue，並標記為已訪問。
• 如果 queue 變為空，則表示沒有找到有效的路徑，回傳 false。

程式

class Solution {
   fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        val graph = buildGraph(edges)
        return hasPathBFS(graph, source, destination)
    }

    private fun buildGraph(edges: Array<IntArray>): Map<Int, List<Int>> {
        val graph = mutableMapOf<Int, List<Int>>()
        edges.forEach { edge ->
            val a = edge[0]
            val b = edge[1]
            graph[a] = (graph[a] ?: emptyList()) + b
            graph[b] = (graph[b] ?: emptyList()) + a
        }
        return graph
    }

    private fun hasPathBFS(graph: Map<Int, List<Int>>, current: Int, target: Int): Boolean {
        val queue: Queue<Int> = LinkedList()
        val visited = mutableSetOf<Int>()
        queue.offer(current)
        visited.add(current)
        while (queue.isNotEmpty()) {
            for (i in queue.indices) {
                val node = queue.poll()
                if (node == target) return true
                graph[node]?.forEach { neighbor ->
                    if (!visited.contains(neighbor)) {
                        if (neighbor == target) return true
                        visited.add(neighbor)
                        queue.offer(neighbor)
                    }
                }
            }
        }
        return false
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是圖中節點的數量， 是圖中邊的數量。我們最多只需要訪問每個節點和每條邊一次，所以時間複雜度為 。

• 空間複雜度:
  ，其中 是圖中節點的數量， 是圖中邊的數量。空間複雜度主要取決於三個部分：graph、visited和 queue。 graph 需要 的空間，visited 需要 的空間，queue 最多需要 的空間。因此，總的空間複雜度為 。

　更多 LeetCode 解答在此，一起來學習！

來，一起準備面試吧！

寫一份超級吸睛的履歷吧！從技術主管的視角，幫助你用精練語句量化成效，讓你的履歷變得更加出色

履歷諮詢	加入讀書會 (邀請碼：2573)