Is There A Route Between Two Nodes Graph Problem | letsbug

     Find Route Between Two Nodes Graph Problem 

    Hi everyone in this article we are going to see how to solve the problem of finding route between two nodes of a graph. 

    Before we start let's make sure that you know a little bit about graphs data structure and how to traverse through a graph. 

code: 

const testG = {
    'A': ['B', 'C'],
    'B': ['D', 'F', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': [],
    'G': []
}
const path = (graph, start, end) => {
    if (start == end) return true
    const queue = [start]
    const visited = {}
    visited[start] = true
    while (queue.length) {
        const node = queue.shift()
        const neighbors = graph[node]
        for (let i = 0; i < neighbors.length; i++) {
            if (!visited[neighbors[i]]) {
                if (neighbors[i] == end) {
                    return true
                } else {
                    visited[neighbors[i]] = true
                    queue.push(neighbors[i])
                }
            }
        }
    }
    return false
}
console.log(path(testG, 'A', 'B'))
console.log(path(testG, 'A', 'C'))
console.log(path(testG, 'A', 'D'))
console.log(path(testG, 'A', 'E'))
console.log(path(testG, 'A', 'F'))
console.log(path(testG, 'F', 'A'))
console.log(path(testG, 'E', 'B'))
console.log(path(testG, 'C', 'A'))
console.log(path(testG, 'C', 'G'))

Explanation:

    In the above code we have a graph data structure called testG and it is represented in adjacency list form. So every key in the testG object is a node and its value is a array which has all the nodes that it is connected to.

    So, next we create a function called path. And takes three arguments i.e graph which is the graph itself and start and end. start is the node from where we want to find the path. And end is the final destination node where we want to go.

    It is a iterative solution so we first check if the start is equal to end and if so then we return true meaning there is a path. Else we create a queue and add our starting node to it. And also create object visited to keep track of the nodes which we have already visited or else we will get in the infinite loop if there is cycle in the graph. 

    And then in the visited object we first add our starting node and set it to true meaning we have visited it and then run a while loop which runs till there are elements in the queue. And for every element in the queue we take the first element of the queue and get its neighbours i.e list of node it is connected to. And we traverse through the list. And check if that node is visited or not.

    And if that node is not visited, we check if that node is equal to our destination node. And if so then we return true else we mark it visited and add it to the queue. And then if there is no element in the queue we return false as there is not way to get to that node.

output: 

$ node routeBetweenNodes.js
true
true
true
true
true
false
false
false
false