Find if Path Exists in Graph

Here’s a high-level approach for the problem:

Approach:

1. 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.

2. 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:

1. Create Adjacency List:

   • Initialize an empty adjacency list representation of the graph.
   • Iterate through the given array of edges.
   • For each edge [a, b], add b to the adjacency list of a, 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.

2. 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.

3. Return Result:

   • After BFS traversal, if the destination node is reached, return true.
   • If the destination node is not reached, return false.

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));