DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on

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

Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up