Leetcode 1971: Find if Path Exists in Graph
You are given a graph with
n vertices labeled from 0 to n-1 (inclusive) and edges connecting pairs of vertices. Your task is to determine if there exists a valid path from a given source vertex to a destination vertex. The graph is undirected, and each pair of vertices is connected by at most one edge. The vertices are connected by edges as given in the input.Problem
Approach
Steps
Complexity
Input: The input consists of the following components: an integer `n`, representing the number of vertices, a 2D array `edges` representing the edges between vertices, and two integers `source` and `destination` which are the starting and ending vertices respectively.
Example: n = 4, edges = [[0,1],[1,2],[2,3]], source = 0, destination = 3
Constraints:
• 1 <= n <= 2 * 10^5
• 0 <= edges.length <= 2 * 10^5
• 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.
Output: The output should be a boolean value, `true` if there is a valid path from the source to the destination vertex, and `false` otherwise.
Example: Output: true
Constraints:
• The solution must be able to handle large graphs efficiently.
Goal: To determine if a valid path exists from the source to the destination vertex by performing a breadth-first search (BFS) or depth-first search (DFS) in the graph.
Steps:
• Step 1: Represent the graph using an adjacency list where each vertex points to a list of connected vertices.
• Step 2: Use BFS (or DFS) starting from the source vertex to explore all reachable vertices.
• Step 3: If the destination vertex is found during the traversal, return `true`.
• Step 4: If the traversal completes without visiting the destination vertex, return `false`.
Goal: The input graph must meet the given constraints for `n`, edges, and vertex values.
Steps:
• The graph is undirected and has no self edges.
• The graph can have up to 200,000 vertices and edges, so an efficient solution is required.
Assumptions:
• The graph is connected and there may be multiple paths from source to destination.
• Input: Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
• Explanation: In this case, there is a direct path from vertex 0 to vertex 2, or a path through vertex 1 (0 -> 1 -> 2), so the output is `true`.
• Input: Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
• Explanation: In this case, there is no path from vertex 0 to vertex 5, so the output is `false`.
Approach: We can approach this problem by performing a graph traversal (BFS or DFS) to check if a path exists between the source and destination vertices. The traversal should explore all connected vertices from the source and check if the destination is reachable.
Observations:
• The problem can be efficiently solved using BFS or DFS to traverse the graph.
• The BFS approach will ensure we explore all possible paths from the source to the destination vertex in the shortest way possible.
Steps:
• Step 1: Build the graph using an adjacency list.
• Step 2: Initialize a queue for BFS and a visited array to keep track of visited vertices.
• Step 3: Perform BFS starting from the source vertex, pushing adjacent vertices to the queue and marking them as visited.
• Step 4: If the destination vertex is visited, return `true`, otherwise continue the search.
• Step 5: If BFS completes without finding the destination vertex, return `false`.
Empty Inputs:
• If there are no edges, and the source is not equal to the destination, the result will be `false`.
Large Inputs:
• For large inputs with up to 200,000 vertices, we need to ensure the solution uses efficient graph traversal.
Special Values:
• When the source and destination vertices are the same, the answer is trivially `true`.
Constraints:
• Ensure that the graph traversal does not exceed time limits for large inputs.
bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
unordered_map<int,vector<int>> graph;
for(auto e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
vector<bool> visited(n,0);
queue<int> q;
q.push(start);
visited[start] = 1;
while(!q.empty()) {
int curr = q.front();
q.pop();
if(curr == end)
return 1;
for(auto &node : graph[curr]){
if(!visited[node]){
visited[node] = 1;
q.push(node);
}
}
}
return false;
}
1 : Function Definition
bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
This is the function signature, defining a function 'validPath' that takes the number of nodes (n), a vector of edges, and two nodes (start, end) to check if a path exists between them.
2 : Graph Construction
unordered_map<int,vector<int>> graph;
Here, an unordered map 'graph' is created to store the adjacency list of the graph, where each node maps to a list of its connected nodes.
3 : Edge Processing
for(auto e : edges) {
This loop iterates through each edge in the input 'edges' list to populate the adjacency list 'graph'.
4 : Add Edge to Graph
graph[e[0]].push_back(e[1]);
This line adds a directed edge from node e[0] to node e[1] in the graph.
5 : Add Edge to Graph
graph[e[1]].push_back(e[0]);
This line adds the reverse edge from node e[1] to node e[0] because the graph is undirected.
6 : Visited Initialization
vector<bool> visited(n,0);
A 'visited' vector of size n is initialized to track whether a node has been visited during traversal.
7 : Queue Initialization
queue<int> q;
A queue is initialized to implement breadth-first search (BFS).
8 : Queue Push Start Node
q.push(start);
The 'start' node is added to the queue to begin BFS.
9 : Mark Start Node as Visited
visited[start] = 1;
The 'start' node is marked as visited.
10 : While Loop
while(!q.empty()) {
The while loop continues as long as there are nodes in the queue to process.
11 : Queue Pop
int curr = q.front();
The node at the front of the queue is assigned to 'curr' for processing.
12 : Queue Pop
q.pop();
The node is removed from the queue after being processed.
13 : Check for End Node
if(curr == end)
If the current node is the 'end' node, a valid path has been found.
14 : Return Path Found
return 1;
Return 1 to indicate that a valid path was found between 'start' and 'end'.
15 : Node Traversal
for(auto &node : graph[curr]){
This loop iterates through all adjacent nodes of the current node.
16 : Check if Node is Visited
if(!visited[node]){
Check if the adjacent node has not been visited yet.
17 : Mark Node as Visited
visited[node] = 1;
Mark the adjacent node as visited.
18 : Queue Push Node
q.push(node);
Add the adjacent node to the queue to continue BFS.
19 : Return No Path
return false;
Return false to indicate that no valid path was found between 'start' and 'end'.
Best Case: O(n + m), where `n` is the number of vertices and `m` is the number of edges
Average Case: O(n + m)
Worst Case: O(n + m)
Description: The time complexity of BFS or DFS is O(n + m), where `n` is the number of vertices and `m` is the number of edges.
Best Case: O(n + m)
Worst Case: O(n + m)
Description: The space complexity is O(n + m) due to the adjacency list and the visited array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus