Find if Path Exists in Graph
Tags: leetcode, datastructures, javascript
Published: 2024-04-21 03:12:48

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.

```js
/**
 * @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));

```