Cracking the Coding Interview - 4.1 Graph Traversal

Question

I'm working through the classic Cracking the Coding Interview book. I'm trying to solve the following graph problem:

4.1) Route Between Nodes: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

I've written a solution in JavaScript and found it was a lot less complicated than the book's solution. Am I missing something? Why does the solution use a Visiting state? Can't we just use Visited instead?

function RouteBetweenNodes( node1, node2 ) {
 const q = new Queue()
 q.add( node1 )
 while ( !q.isEmpty() ) {
 const node = q.remove()
 if ( node === node2 ) {
 return true 
 }
 node.visited = true
 node.children.forEach( child => !child.visited && q.add( child ) )
 }
 return false 
}

Here is an implementation of a Queue for completeness:

class QueueNode {
 constructor( data ) {
 this.data = data
 this.next = null
 }
}
class Queue {
 constructor() {
 this.first = null
 this.last = null
 }
 add( item ) {
 const newNode = new QueueNode( item )
 if ( this.last ) {
 this.last.next = newNode
 } else {
 this.first = newNode
 }
 this.last = newNode
 }
 remove() {
 if ( this.first ) {
 const data = this.first.data
 this.first = this.first.next
 if ( this.first == null ) {
 this.last == null
 }
 return data
 }
 throw Error( 'empty queue' )
 }
 peek() {
 if ( this.first ) {
 return this.first.data
 }
 throw Error( 'empty queue' )
 }
 isEmpty() {
 return this.first === null 
 }
}

Here is the book's solution.

• Phrancis: Welcome to Code Review! I hope you get some good answers =)
• vnp: The Visiting state lets you tell apart nodes waiting in the queue from the truly uncharted nodes. Without such state the same node may be added multiple times. It hurts performance, and in some (very contrived) cases may even lead to incorrectness.
• hoffmale: @vnp I can't see a case where it would lead to incorrect results. Can you elaborate?
• vnp: @hoffmale On a specially crafted infinite graph, with some nodes having infinitely many inbound edges, the algorithm would fail to find a surely existing path, whereas a book solution would succeed. Pretty contrived, as I said.
• Sᴀᴍ Onᴇᴌᴀ: It appears that the code in the image is Java, but your code is Javascript (or at least you used the tag javascript)... is that intentional?

Answer 1

• Your worst case performance (every node is connected to each other node but node2) is \$\mathcal{O}(n^2)\,ドル up from the "normal" \$\mathcal{O}(n)\,ドル because nodes can be added to the queue multiple times. This should also increase the average runtime. This gets even worse if multiple edges between any 2 nodes are allowed.

  Note that adding another check q.contains(node) would still result in a runtime of \$\mathcal{O}(n^2)\$ as those checks add a factor of \$\mathcal{O}(n)\$. The Visiting state prevents this.

• visited is never reset to false (in the presented code). This will lead to errors in subsequent calls.

• The definition of Queue is missing.