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 <stdbool.h>
2#include <stdlib.h>
3
4void dfs(int node, int **adjList, int *adjListSize, bool *visited) {
5 visited[node] = true;
6 for (int i = 0; i < adjListSize[node]; i++) {
7 int neighbor = adjList[node][i];
8 if (!visited[neighbor]) {
9 dfs(neighbor, adjList, adjListSize, visited);
10 }
11 }
12}
13
14bool validPath(int n, int **edges, int edgesSize, int *edgesColSize, int source, int destination) {
15 if (source == destination) return true;
16
17 // Create adjacency list
18 int *adjListSize = calloc(n, sizeof(int));
19 int **adjList = malloc(n * sizeof(int *));
20
21 for (int i = 0; i < n; i++) {
22 adjList[i] = malloc(0);
23 }
24
25 for (int i = 0; i < edgesSize; i++) {
26 int u = edges[i][0];
27 int v = edges[i][1];
28
29 adjListSize[u]++;
30 adjListSize[v]++;
31
32 adjList[u] = realloc(adjList[u], adjListSize[u] * sizeof(int));
33 adjList[v] = realloc(adjList[v], adjListSize[v] * sizeof(int));
34
35 adjList[u][adjListSize[u] - 1] = v;
36 adjList[v][adjListSize[v] - 1] = u;
37 }
38
39 bool *visited = calloc(n, sizeof(bool));
40
41 dfs(source, adjList, adjListSize, visited);
42
43 bool result = visited[destination];
44
45 // Free memory
46 for (int i = 0; i < n; i++) {
47 free(adjList[i]);
48 }
49 free(adjList);
50 free(adjListSize);
51 free(visited);
52
53 return result;
54}This C implementation of the DFS approach creates an adjacency list from the given edge list. It uses a recursive depth-first search to explore the graph, marking nodes as visited. The search begins at the source and continues until it either finds the destination or runs out of vertices to explore. If the destination is found, the function returns true; otherwise, it returns false. The adjacency list is implemented with dynamic memory allocation to store neighboring vertices efficiently.
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.
#include <numeric>
using namespace std;
class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) {
rank = vector<int>(n, 0);
parent = vector<int>(n);
iota(parent.begin(), parent.end(), 0);
}
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]);
}
return parent[node];
}
void unionSet(int u, int v) {
int pu = find(u);
int pv = find(v);
if (rank[pu] > rank[pv]) {
parent[pv] = pu;
} else if (rank[pu] < rank[pv]) {
parent[pu] = pv;
} else {
parent[pu] = pv;
rank[pv]++;
}
}
};
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
UnionFind uf(n);
for (const auto& edge : edges) {
uf.unionSet(edge[0], edge[1]);
}
return uf.find(source) == uf.find(destination);
}This solution uses a Union-Find class in C++, where each node initially acts as its own parent. Union by rank is applied to link trees efficiently, ensuring a flat structure which is further enhanced by path compression implemented in the `find` method. The core loop processes each edge in the graph and adds connections where necessary. The final comparison checks the root components of source and destination.