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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public boolean validPath(int n, int[][] edges, int source, int destination) {
6 if (source == destination) return true;
7
8 List<List<Integer>> adjList = new ArrayList<>();
9 for (int i = 0; i < n; i++) {
10 adjList.add(new ArrayList<>());
11 }
12
13 for (int[] edge : edges) {
14 adjList.get(edge[0]).add(edge[1]);
15 adjList.get(edge[1]).add(edge[0]);
16 }
17
18 boolean[] visited = new boolean[n];
19 return dfs(source, destination, adjList, visited);
20 }
21
22 private boolean dfs(int node, int destination, List<List<Integer>> adjList, boolean[] visited) {
23 if (node == destination) return true;
24 if (visited[node]) return false;
25
26 visited[node] = true;
27 for (int neighbor : adjList.get(node)) {
28 if (dfs(neighbor, destination, adjList, visited)) return true;
29 }
30
31 return false;
32 }
33}This Java solution uses DFS with recursive calls to navigate through the graph. After constructing an adjacency list to represent the graph, the DFS method is employed to traverse the graph from the source vertex. If the destination vertex is reached, the function returns true; otherwise, it goes through each adjacent vertex recursively.
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 JavaScript deployment uses the Union-Find structure to ascertain connectivity through graph components' union and determination. Components are united efficiently with path compression and rank-based decisions, ensuring a low operational cost for connectivity verification. By confirming shared roots for source and destination, it validates the path's existence renderings.