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.

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.