LeetCode: 1971-Find if Path Exists in Graph 解題紀錄

Last Updated on 2022-12-19 by Clay

題目

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Constraints:

• 1 <= n <= 2 * 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= source, destination <= n - 1
• There are no duplicate edges.
• There are no self edges.

題目會輸入一個無向圖和起點、終點，我們要做的就是判斷起點和終點是否有連接在一起。

---

解題思路

BFS

1. 建立一個字典（int -> bool）保存節點是否已經走過
2. 建立一個字典（int -> array<int>）保存節點連接的所有節點
3. 建立一個佇列（queue）保存當前一層所要拜訪的所有節點
4. 依序讀出佇列中當前一層所要拜訪的所有節點，同時把每個節點的狀態透過第一個字典儲存成 true 代表已經走完；同時也判斷當前節點是否剛好為目標節點、以及當前節點所連接的所有節點要再儲存回佇列中代表下一層要走的節點
5. 如果完全遍歷完發現從未發現目標節點，則回傳 false。

詳細做法可以參考範例程式碼。

BFS 複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // Init
        queue<int> q({source});
        unordered_map<int, vector<int>> mp;
        unordered_map<int, bool> isVisited({{source, true}});
        for (auto& edge: edges) {
            mp[edge[0]].emplace_back(edge[1]);
            mp[edge[1]].emplace_back(edge[0]);
        }

        // Find the path
        while (!q.empty()) {
            int size = q.size();

            for (int i=0; i<size; ++i) {
                int vertex = q.front();
                q.pop();
                isVisited[vertex] = true;
                
                if (vertex == destination) {
                    return true;
                }

                for (int& v: mp[vertex]) {
                    if (isVisited[v]) {
                        continue;
                    }

                    q.push(v);
                }
            }
        }

        return false;
    }
};

Python 範例程式碼

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        # Init
        q = [source]
        is_visited = {source: True}
        mp = {v: [] for v in range(n)}
        for edge in edges:
            mp[edge[0]].append(edge[1])
            mp[edge[1]].append(edge[0])

        # Find the path
        while q:
            size = len(q)
            for i in range(size):
                vertex = q[0]
                q = q[1:]
                
                is_visited[vertex] = True

                if vertex == destination:
                    return True

                for v in mp[vertex]:
                    if is_visited.get(v, False):
                        continue

                    q.append(v)

        return False

---

References

• 1971. Find if Path Exists in Graph

---

Read More

• LeetCode 解題紀錄目錄