Skip to main content

< Back to Data Structures and Algorithms

Graph Algorithms · Graphs

Has Path (Directed Acyclic Graph)

Whether one node can reach another along a directed graph's edges, searched depth first by recursion or breadth first with a queue.

Step through it

Examples
Edge cases
graph
fgihkj

current = "f"dst = "k"

Step 0 of 12

Output

Running… play or step to the end.

The code

/* These algorithms navigate through a Directed Acyclic Graph and determine if 
 * a path exists between the provided source and destination nodes.
 *
 * Below are two examples: Depth First Search, and Breadth First Search.
 */

// Depth First Search approach.
const hasPathDFS = (graph, current, dst) => {
  /* 'current' can also be referred to as 'source', 
     this algorithm is initialised with a 'source', but as it recurses, the 
     'current' node replaces the 'source'. */

  // A path exists when the current node matches the destination.
  if (current === dst) return true

  // Iterate over each neighbour of the current node.
  for (let neighbour of graph[current]) {
    // Recursively call this method on each neighbour node. If a match is found...
    if (hasPathDFS(graph, neighbour, dst) === true) {
      // Bubble up a 'true' response through each call on the call stack.
      return true
    }
  }

  // Recursed through every edge combination. A path doesn't exist.
  return false
}

// Breadth First Search approach.
const hasPathBFS = (graph, src, dst) => {
  // Initialise a queue data structure, setting 'src' as its' initial value.
  const queue = [ src ]

  // While the queue is still populated.
  while (queue.length) {
    // Take the left-most node off the queue.
    const current = queue.shift()

    // The node matches the destination. A path exists.
    if (current === dst) return true

    // Iterate over every neighbour of the node.
    for (let neighbour of graph[current]) {
      // Add them to the queue.
      queue.push(neighbour)
    }
  }

  // A path doesn't exist.
  return false
}

// A Directed Acyclic Graph, represented as an adjacency list.
const graph = {
  f: ['g', 'i'],
  g: ['h'],
  h: [],
  i: ['g', 'k'],
  j: ['i'],
  k: [],
}

hasPathDFS(graph, 'f', 'k')
hasPathBFS(graph, 'f', 'k')

The original on GitHub (opens in a new tab)