Here's a high-level 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 breadth-first 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)