Find if there is a path between two vertices in a directed graph in Javascript

Question

I have written a code in javascript to check is there any path between two vertices of a graph

To test my code I have run it on following sample graph data

Graph Map {
  1 => [ 2, 3, 4 ],
  2 => [ 1, 3 ],
  3 => [ 1, 2, 4, 5 ],
  4 => [ 1, 3, 5 ],
  5 => [ 3, 4 ]
}

I am using Depth-first-search algorithm to travers through each node of the above graph

• First I am creating Adjacent List from given edgeList
• Then I am applying dfs on Adjacent List
  • Visiting the starting node
  • Exploring all its children

class Graph {
    constructor() {
        this.adjList = new Map();
    }

    addVertex(v) {
        this.adjList.set(v, []);
    }

    addEdge(v, e) {
        this.adjList.get(v).push(e)
    }

    createAdjList(edgeList) {
        edgeList.forEach(edge => {
            this.addVertex(edge[0]);
            this.addVertex(edge[1]);
        })

        edgeList.forEach(edge => {
            this.addEdge(edge[0], edge[1]);
            this.addEdge(edge[1], edge[0])
        })
    }

    hasPath(start, end, visited = {}) {

        // base condition
        if (start == end) return true;

        visited[start] = true;
        const childrens = this.adjList.get(start);

        childrens.forEach(node => {
            if (!visited[node]) {
                var result = this.hasPath(node, end, visited);
                if (result) {
                    return true;
                }
            }
        })
        return false
    }
}

const graph = new Graph();
const edgeList = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [3, 5], [4, 5]];
graph.createAdjList(edgeList)

console.log("Has Path", graph.hasPath(1, 4))

but in place returning true it is returning false, I don't understand what is the mistake I have did it in my code

Answer 1

It was said around million times probably on stackoveflow, but:

When you do:

[1, 2, 3].forEach(() => {
  return true
})

What you really do is - create a new anonymous function

const fn = () => {
  return true
}
[1, 2, 3].forEach(fn)

And returning from anonymous function doesn't return from parent function

Just use a normal loop:

class Graph {
  constructor() {
    this.adjList = new Map();
  }

  addVertex(v) {
    this.adjList.set(v, []);
  }

  addEdge(v, e) {
    this.adjList.get(v).push(e)
  }

  createAdjList(edgeList) {
    edgeList.forEach(edge => {
      this.addVertex(edge[0]);
      this.addVertex(edge[1]);
    })

    edgeList.forEach(edge => {
      this.addEdge(edge[0], edge[1]);
      this.addEdge(edge[1], edge[0])
    })
  }

  hasPath(start, end, visited = {}) {
    console.log(start, end, visited)

    // base condition
    if (start == end) return true;

    visited[start] = true;
    const childrens = this.adjList.get(start);

    for (const node of childrens) {
      if (!visited[node]) {
        var result = this.hasPath(node, end, { ...visited });
        if (result) {
          return true;
        }
      }
    }
    return false
  }
}

const graph = new Graph();
const edgeList = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 3],
  [3, 4],
  [3, 5],
  [4, 5]
];
graph.createAdjList(edgeList)

console.log("Has Path", graph.hasPath(1, 4))

P.S.

I also destructured your visited variable, but I'm not sure it it's possible in you algorithm