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.
1var validPath = function(n, edges, source, destination) {
2 if (source === destination) return true;
3
4 const adjList = Array.from({length: n}, () => []);
5
6 for (let [u, v] of edges) {
7 adjList[u].push(v);
8 adjList[v].push(u);
9 }
10
11 const visited = new Array(n).fill(false);
12
13 const dfs = (node) => {
14 if (node === destination) return true;
15 if (visited[node]) return false;
16
17 visited[node] = true;
18
19 for (let neighbor of adjList[node]) {
20 if (dfs(neighbor)) return true;
21 }
22 return false;
23 }
24
25 return dfs(source);
26};This JavaScript function uses DFS to explore paths in the graph. An adjacency list is employed to represent graph connections, and recursion performs the depth-first exploration. The visited array is used to track which nodes have been checked, ensuring efficiency by preventing redundant visits.
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.
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
public bool ValidPath(int n, int[][] edges, int source, int destination) {
UnionFind uf = new UnionFind(n);
foreach (var edge in edges) {
uf.Union(edge[0], edge[1]);
}
return uf.Find(source) == uf.Find(destination);
}
}This C# program employs the Union-Find pattern using classes to ensure disjoint set fusion and path checks efficiently. Path compression boosts search speed, while union by rank minimizes height. The algorithm ensures source and destination belong to the same root component, forming the basis for determining path existence.