trjhtr

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.

• 
  

  Your worst case performance (every node is connected to each other node but node2) is $mathcalO(n^2)$, up from the "normal" $mathcalO(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 $mathcalO(n^2)$ as those checks add a factor of $mathcalO(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.