【LeetCode】 1971. Find if Path Exists in Graph

Description

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.

有一個包含 n 個頂點的雙向圖，每個點被標記成 0 到 n - 1 (包含)。圖中的邊使用二維整數陣列 deges 表示，edges[i] = [ui, vi] 表示一條在頂點 ui 和 vi 的雙向邊。每個頂點對之間只會有一條邊，且不會有點自己連結到自己。
你需要判斷從頂點 source 到 destnation 之間是否存在一條合法路徑。
給予 edges 和整數 n、source 和 destination，回傳 true 如果 source 到 destination 之間有一條合法路徑，否則回傳 false。

Example:

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.

Solution

• 標準的 DFS/BFS 題目
• 先建立好圖中每個節點的關係，然後每個點遍歷一次即可
• 為了節省時間，節點中加入了 touched 屬性，代表該點是否已經走過
  • 走過的路就不要再走
• 下面範例中，BFS 演算法多宣告了 vector<node> stack 去記錄目前的待走節點
  • 如果改用遞迴的方式實作 DFS，直接在 function stack 中完成紀錄，可以節省一些空間資源

Code

class Solution {
public:
    struct node
    {
        int name;
        vector<int> next;
        bool touched;
    };

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        if(source == destination)
            return true;
        vector<node> nodes;
        for(int i = 0; i < n; i++)
        {
            node temp;
            temp.name = i;
            temp.touched = false;
            nodes.push_back(temp);
        }
        for(int i = 0; i < edges.size(); i++)
        {
            int a = edges[i][0];
            int b = edges[i][1];
            nodes[a].next.push_back(b);
            nodes[b].next.push_back(a);
        }
        //BFS
        vector<node> stack;
        stack.push_back(nodes[source]);
        while(!stack.empty())
        {
            for(int i = 0; i < stack.front().next.size(); i++)
            {
                if(stack.front().next[i] == destination)
                    return true;
                else if(nodes[stack.front().next[i]].touched == false)
                {
                    nodes[stack.front().next[i]].touched = true;
                    stack.push_back(nodes[stack.front().next[i]]);
                }
            }
            stack.erase(stack.begin());
        }
        return false;
    }
};

tags: LeetCode C++