Here's a highlevel approach for the problem:
Approach:

Create an Adjacency List:
 Convert the given array of edges into an adjacency list representation of the graph.
 This helps in efficiently representing and traversing the graph.

Check Path Existence:
 Use a breadthfirst search (BFS) approach to check if there exists a path from the source node to the destination node.
 Start with the source node and explore its neighbors level by level.
 Keep track of visited nodes to avoid revisiting them.
 If the destination node is reached during the BFS traversal, return
true
, indicating that a path exists.  If all reachable nodes are explored and the destination node is not found, return
false
, indicating that no path exists.
Detailed Steps:

Create Adjacency List:
 Initialize an empty adjacency list representation of the graph.
 Iterate through the given array of edges.
 For each edge
[a, b]
, addb
to the adjacency list ofa
, and vice versa (since it's an undirected graph).  Ensure that each node is added to the adjacency list even if it doesn't have any neighbors.

Check Path Existence (BFS):
 Initialize a queue and a visited array.
 Enqueue the source node into the queue and mark it as visited.
 While the queue is not empty:
 Dequeue a node from the queue.
 If the dequeued node is the destination, return
true
.  Otherwise, enqueue all unvisited neighbors of the dequeued node into the queue and mark them as visited.
 If the destination node is not reached after exploring all reachable nodes, return
false
.

Return Result:
 After BFS traversal, if the destination node is reached, return
true
.  If the destination node is not reached, return
false
.
 After BFS traversal, if the destination node is reached, return
Time Complexity:
 Creating the adjacency list: O(E), where E is the number of edges.
 BFS traversal: O(V + E), where V is the number of vertices and E is the number of edges.
 Overall time complexity: O(V + E), where V is the number of vertices and E is the number of edges.
This approach efficiently determines whether there exists a path between the given source and destination nodes in the graph.
/**
* @param {number} n
* @param {number[][]} edges
* @param {number} source
* @param {number} destination
* @return {boolean}
*/
var validPath = function (n, edges, source, destination) {
const graph = getAdjList(edges);
const pathExists = checkIfPathExists(graph, source, destination, n);
return pathExists;
};
const getAdjList = (edges) => {
const graph = new Map();
// create our adjacency list
edges.forEach(([a, b]) => {
if (!graph.has(a)) {
graph.set(a, []);
}
if (!graph.has(b)) {
graph.set(b, []);
}
graph.get(a).push(b);
graph.get(b).push(a);
});
return graph;
};
const checkIfPathExists = (graph, source, destination, n) => {
// prevent revisiting nodes
const visited = new Array(n);
const queue = [source];
while (queue.length > 0) {
const node = queue.shift(); // this is an O(n) operation here. if we used a real queue the dequeue method would be O(1)
if (node === destination) {
return true;
}
if (!visited[node]) {
visited[node] = true;
graph.get(node).forEach((neighbor) => {
if (!visited[neighbor]) {
queue.push(neighbor);
}
});
}
}
return false;
};
console.log(validPath(10, [[4, 3], [1, 4], [4, 8], [1, 7], [6, 4], [4, 2], [7, 4], [4, 0], [0, 9], [5, 4]], 5, 9));
Top comments (0)