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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public bool ValidPath(int n, int[][] edges, int source, int destination) {
6 if (source == destination) return true;
7
8 var adjList = new List<int>[n];
9 for (var i = 0; i < n; i++) {
10 adjList[i] = new List<int>();
11 }
12
13 foreach (var edge in edges) {
14 adjList[edge[0]].Add(edge[1]);
15 adjList[edge[1]].Add(edge[0]);
16 }
17
18 var visited = new bool[n];
19
20 return Dfs(source, destination, adjList, visited);
21 }
22
23 private bool Dfs(int current, int destination, List<int>[] adjList, bool[] visited) {
24 if (current == destination) return true;
25 if (visited[current]) return false;
26
27 visited[current] = true;
28
29 foreach (var neighbor in adjList[current]) {
30 if (Dfs(neighbor, destination, adjList, visited)) return true;
31 }
32
33 return false;
34 }
35}This C# solution utilizes depth-first search employing recursion to determine connectivity between the source and destination vertices. The adjacency list provides the graph's structure, while a boolean array tracks visited vertices, ensuring the search does not revisit nodes unnecessarily.
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 C code implements the Union-Find data structure with path compression and union by rank. Initially, each node is its own parent. The `find` function implements path compression to flatten the structure for efficient look-up, while the `unionSets` function connects components, using rank optimization to keep the tree flat. After processing all edges, the function performs a final check to see if the source and destination belong to the same connected component.