1971. Find if Path Exists in Graph

有一個具有 n個頂點的 雙向 圖，其中每個頂點標記從 0 到 n - 1（包含 0 和 n - 1）。圖中的邊用一個二維整數數組 edges 表示，其中 edges[i] = [ui, vi] 表示頂點 ui 和頂點 vi 之間的雙向邊。 每個頂點對由 最多一條 邊連接，并且沒有頂點存在與自身相連的邊。

請你確定是否存在從頂點 start 開始，到頂點 end 結束的 有效路徑 。

給你數組 edges 和整數 n、start和end，如果從 start 到 end 存在 有效路徑 ，則返回 true，否則返回 false 。

示例 1：輸入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2 輸出：true 解釋：存在由頂點 0 到頂點 2 的路徑: - 0 → 1 → 2 - 0 → 2示例 2：輸入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5 輸出：false 解釋：不存在由頂點 0 到頂點 5 的路徑.

提示:

• 1 <= n <= $2?10^5$
• 0 <= edges.length <= $2?10^5$
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= start, end <= n - 1
• 不存在雙向邊
• 不存在指向頂點自身的邊

解題思路

使用map維護雙向圖邊之間的關系，key為節點編號，value為一個記錄與當前節點存在公共邊連接的節點數組。

利用隊列實現廣度優先搜索，先將start節點入隊，每次從隊列中取出隊首節點，將與該節點存在公共邊并且沒被訪問過的節點入隊，直到找出end節點為止，如果直到隊列為空都找不到end節點，說明不存在從 start 到 end 的 有效路徑

代碼

class Solution { public:bool validPath(int n, vector<vector<int>>& edges, int start, int end) {map<int,vector<int>> e;for(auto item:edges){e[item[0]].push_back(item[1]);e[item[1]].push_back(item[0]);}unordered_set<int> s;s.insert(start);queue<int>q;q.push(start);while (!q.empty()){int cur=q.front();q.pop();if (cur==end)return true;for (auto c:e[cur]) {if (!s.count(c)){q.push(c);s.insert(c);}}}return false;} };

總結

以上是生活随笔為你收集整理的1971. Find if Path Exists in Graph的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。