CODEWITHSUNDEEP
javascriptalgorithmgraph
Bunny Rabbit
Bunny Rabbit

Reputation: 8411

recursion in JavaScript graph exploring algorithm

I am trying to explore a graph here but I am not sure what is wrong with the explore function. The recursion doesn't seem to be working correctly; while exploring the neighbours of the node 0 it explored 0, 1, 2 and then never returns back to explore 3, 4, 5; why is that so?

explored=[]
//class definition 
function graph(){
    this.graph=new Array();
    this .graph[0] = [1,0,1,1,0,1]
    this .graph[1] = [0,1,1,1,0,0]
    this .graph[2] = [1,1,1,1,0,0]
    this .graph[3] = [1,1,1,1,1,0]
    this .graph[4] = [0,0,0,1,1,0]
    this .graph[5] = [1,0,0,0,0,0]

    this.explore    = explore

}

function explore(node,depth){

    explored[node]=1
    document.write('<br>')
    for(x=0;x<depth;x++)
        document.write('-')
    document.write(node+'<br>')
    neighbours=this.graph[node]

    document.write('exploring '+node +' neighbours' + neighbours +'explored = '+explored)

    for ( i=0;i<neighbours.length;i++){
        document.write('checking'+i+' node is ='+node )
        if(neighbours[i] ==1 && explored[i]!=1)
            this.explore(i,++depth)
    }

}

g = new graph()
g.explore(0,0)

Upvotes: 1

Views: 519

Answers (2)

Zachary K
Zachary K

Reputation: 3335

The line this.explore(i,++depth) may also be causing you problems, as you are incrementing depth in the current scope as well as passing the incremented value to the recusive call,

better to use 

this.explore(i, depth + 1);

When in doubt with javascript it is always good to check the code with jslint.

Upvotes: 2

generalhenry
generalhenry

Reputation: 17319

by leaving out var you're setting global variables in a recursive function and stepping on your toes, here's the corrected code

function explore(node,depth){

    explored[node]=1
    document.write('<br>')
    for(**var** x=0;x<depth;x++)
        document.write('-')
    document.write(node+'<br>')
    **var** neighbours=this.graph[node]

    document.write('exploring '+node +' neighbours' + neighbours +'explored = '+explored)

    for (**var** i=0;i<neighbours.length;i++){
        document.write('checking'+i+' node is ='+node )
        if(neighbours[i] ==1 && explored[i]!=1)
            this.explore(i,++depth)
    }

}

Upvotes: 4

Related Questions