Sponsored
Sponsored
The DFS approach involves exploring as far as possible along each branch before backing up. Start from the source vertex and explore each adjacent vertex, marking visited vertices. If you reach the destination during your exploration, return true. If no path to destination is found by the time all possible vertices are visited, return false.
Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges, due to the need to traverse the entire graph in the worst case.
Space Complexity: O(V + E) for storing the adjacency list and the visited array.
1#include <vector>
2using namespace std;
3
4void dfs(int node, vector<vector<int>>& adjList, vector<bool>& visited) {
5 if (visited[node]) return;
6 visited[node] = true;
7 for (int neighbor : adjList[node]) {
8 dfs(neighbor, adjList, visited);
9 }
10}
11
12bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
13 if (source == destination) return true;
14
15 vector<vector<int>> adjList(n);
16 for (auto& edge : edges) {
17 adjList[edge[0]].push_back(edge[1]);
18 adjList[edge[1]].push_back(edge[0]);
19 }
20
21 vector<bool> visited(n, false);
22 dfs(source, adjList, visited);
23
24 return visited[destination];
25}This C++ implementation leverages DFS to explore the graph. An adjacency list is constructed to enable efficient traversal of each vertex's neighbors. Recursion is used to perform the deep search, marking each vertex as visited upon entry. The approach checks if the path exists from the source to the destination by verifying the destination's visit status after the recursion completes. Considerations for edge cases, such as the source being the destination, are also included.
The Union-Find approach is effective for problems involving connectivity checks among different components. This data structure helps efficiently merge sets of connected components and determine whether two vertices are in the same connected component by checking if they share the same root. Initialize each vertex as its own component, then loop through the edges to perform union operations, connecting the components. Finally, check if the source and destination vertices belong to the same component.
Time Complexity: O(Eα(V)), where α is the Inverse Ackermann function which grows very slowly. Equivalent to O(E) practically.
Space Complexity: O(V) for storing parent and rank arrays.
This Java implementation uses the Union-Find data structure with union by rank and path compression. All nodes start out in their own component. The `union` function merges two components, striving for minimal tree height using rank information. This code efficiently connects components via edges and verifies connectivity between source and destination by checking root parents.