Problem Statement
Given an undirected graph, represented as a list of edges. Each edge is illustrated as a pair of integers [u, v], signifying that there's a mutual connection between node u and node v.
You are also given starting node start, and a destination node end, return true if a path exists between the starting node and the destination node. Otherwise, return false.
Examples
Example 1:
- Input: n =
4, edges =[[0,1],[1,2],[2,3]], start =0, end =3
- Expected Output:
true - Justification: There's a path from node 0 -> 1 -> 2 -> 3.
Example 2:
- Input: n =
4, edges =[[0,1],[2,3]], start =0, end =3
- Expected Output:
false - Justification: Nodes 0 and 3 are not connected, so no path exists between them.
Example 3:
- Input: n =
5, edges =[[0,1],[3,4]], start =0, end =4
- Expected Output:
false - Justification: Nodes 0 and 4 are not connected in any manner.
Constraints:
- 1 <= n <= 2 * 10<sup>5</sup>
- 0 <= edges.length <= 2 * 10<sup>5</sup>
- edges[i].length == 2
- 0 <= u<sub>i</sub>, v<sub>i</sub> <= n - 1
- u<sub>i</sub> != v<sub>i</sub>
- 0 <= source, destination <= n - 1
- There are no duplicate edges.
- There are no self edges.
Why this is a Graph problem
| What the question says | The signal it matches |
|---|---|
| "represented as a list of edges" | the input is a list of pairs that you must turn into an adjacency list first |
| "if a path exists between the starting node" | the question asks whether things are connected |
This is the is there a route variant: stop as soon as the target is reached.
The closest alternative. Union Find also answers this. Join the two nodes of every edge into one group, then check whether start and end share a group. The introduction says it is usually simpler when only the group matters, and that is the case here.
A traversal is just as direct. Build the adjacency list, explore outward from start, and stop the moment end appears. It also prepares you for the natural follow-up, which is to return the path itself. A group structure cannot answer that, because it remembers membership and forgets the roads.
Solution
The task at hand is to determine if there's a path from a starting node to an ending node in a given undirected graph. Our approach uses Depth First Search (DFS) to explore the graph recursively. Starting at the initial node, we'll dive as deep as possible into its neighboring nodes. If we reach the target node at any point during the traversal, we know a path exists. If we exhaust all possible routes and haven't found the target, then no path exists.
-
Graph Representation: We'll begin by converting the provided edge list into an adjacency list to represent our graph. The adjacency list is essentially an array (or list) of lists, where each index corresponds to a node, and its content is a list of neighbors for that node. Since our graph is undirected, if there's an edge between nodes A and B, both A will be in B's list and B in A's list.
-
Depth First Search (DFS): With our graph ready, we then use a recursive DFS function to traverse the graph. This function starts at the given node, and if it's the target node, we return true. Otherwise, we mark this node as visited and call the DFS function on all its unvisited neighbors. This dives deeper into the graph. If any of these recursive calls return true (meaning they found the target), our current DFS call also returns true.
-
Handling Cycles: To avoid getting stuck in a loop, especially in cyclic graphs, we keep track of which nodes we've visited. Before exploring a node, we'll check if it's been visited; if it has, we'll skip it.
-
Result: If our DFS exploration reaches the target node, we return true, signifying that a path exists. Otherwise, after checking all paths from the starting node and not finding the target, we'll conclude and return false.
Algorithm Walkthrough
The input is a list of edges, which says nothing about any one node. So each edge is filed under BOTH of its nodes, because the graph is undirected. Now asking "who is next to 2" is one lookup. Before this step it meant scanning every edge. Nearly every graph problem starts here.
1 of 7
Code
Here is the code for this algorithm:
Time Complexity
-
Graph Construction: Constructing the adjacency list from the given edge list takes O(E), where E is the number of edges. Each edge is processed once.
-
DFS Traversal: In the worst-case scenario, the Depth-First Search (DFS) can traverse all nodes and all edges once. This traversal has a time complexity of O(V + E), where V is the number of vertices or nodes, and E is the number of edges.
Combining the above, our time complexity is dominated by the DFS traversal, making it O(V + E).
Space Complexity
-
Graph Representation: The adjacency list requires O(V + E) space.
-
Visited Set/Array: The visited set (or array) will take O(V) space, as it needs to track each node in the graph.
-
Recursive Call Stack: The DFS function is recursive, and in the worst case (for a connected graph), it can have V nested calls. This would result in a call stack depth of V, adding O(V) space complexity.
The dominant factor here is the graph representation and the call stack, so the total space complexity is O(V + E).
Summary:
- Time Complexity: O(V + E)
- Space Complexity: O(V + E)
This makes our algorithm efficient, especially for sparse graphs (i.e., graphs with relatively fewer edges compared to nodes). The worst-case scenario is when the graph is fully connected, but even then, our algorithm is designed to handle it within reasonable limits.
.....
.....
.....