i'm implementing dfs iterative search through matrix via stack generate maze later. thing getting stuck pushing first element without ever popping it:
void dfs_i(int i, int j){ // receives starting position ij aux = new ij (i,j); int [][] movement = {{0,1},{1,0},{0,-1},{-1,0}}; stack <ij> stack = new stack(); stack.push(aux); double random; while(!stack.empty()){ ij temp = (ij)stack.peek(); stack.pop(); //random=(math.random()*4); //system.out.println("stack size "+ stack.size()); /* int index = 0; if ((random>=0)&&(random<1)) index = 1; else if((random >= 1) && (random < 2)) index = 2; else if (random>3) index = 3; int x = temp.i + movement[index][0]; int y = temp.j + movement[index][1]; while(x<0 || x>=m || y<0 || y>=n){ random=(math.random()*4); index = 0; if ((random>=0)&&(random<1)) index = 1; else if((random >= 1) && (random < 2)) index = 2; else if (random>3) index = 3; x = temp.i + movement[index][0]; y = temp.j + movement[index][1]; }*/ for(int k = 0; k<4; k++){ system.out.println("k =" +k); int x = temp.i + movement[k][0]; system.out.println("x =" +x); int y = temp.j + movement[k][1]; system.out.println("y =" +y); if(x<0 || x>=m || y<0 || y>=n)continue; if(adjacencymatrix[x][y]==0)continue; orderofvisits.add(new ij(x,y)); stack.push(new ij(x,y)); adjacencymatrix[temp.i][temp.j] = 0; system.out.println("visited "+ x + " "+ y); } } } full code:
/* * change template, choose tools | templates * , open template in editor. */ package nuevolaberinto; import java.util.arraylist; import java.util.stack; /** * * @author talleres */ class ij { int i; int j; ij (int i,int j){ = this.i; j= this.j; visited=false; } boolean visited; } class graph { int m; int n; int adjacencymatrix[][]; arraylist <ij> orderofvisits; graph(int m,int n){ this.m=m; this.n=n; adjacencymatrix=new int[m][n]; (int i=0; i<m; i++) (int j=0;j<n;j++){ adjacencymatrix[i][j]=-1; //mark vertices not visited } orderofvisits = new arraylist<ij>(); } void dfs_i(int i, int j){ // receives starting position ij aux = new ij (i,j); int [][] movement = {{0,1},{1,0},{0,-1},{-1,0}}; stack <ij> stack = new stack(); stack.push(aux); double random; while(!stack.empty()){ ij temp = (ij)stack.peek(); stack.pop(); //random=(math.random()*4); //system.out.println("stack size "+ stack.size()); /* int index = 0; if ((random>=0)&&(random<1)) index = 1; else if((random >= 1) && (random < 2)) index = 2; else if (random>3) index = 3; int x = temp.i + movement[index][0]; int y = temp.j + movement[index][1]; while(x<0 || x>=m || y<0 || y>=n){ random=(math.random()*4); index = 0; if ((random>=0)&&(random<1)) index = 1; else if((random >= 1) && (random < 2)) index = 2; else if (random>3) index = 3; x = temp.i + movement[index][0]; y = temp.j + movement[index][1]; }*/ for(int k = 0; k<4; k++){ system.out.println("k =" +k); int x = temp.i + movement[k][0]; system.out.println("x =" +x); int y = temp.j + movement[k][1]; system.out.println("y =" +y); if(x<0 || x>=m || y<0 || y>=n)continue; if(adjacencymatrix[x][y]==0)continue; orderofvisits.add(new ij(x,y)); stack.push(new ij(x,y)); adjacencymatrix[temp.i][temp.j] = 0; system.out.println("visited "+ x + " "+ y); } } } void dfs(int i, int j){ // i,j identifies vertex boolean northvalid= false; boolean southvalid= false; boolean eastvalid = false; boolean westvalid = false; int inorth, jnorth; int isouth, jsouth; int ieast, jeast; int iwest, jwest; inorth=i-1; if (!(inorth<0)) northvalid=true; isouth=i+1; if(!((isouth)>=m)) southvalid=true; jeast=j+1; if(!((jeast)>=n)) eastvalid=true; jwest= j-1; if (!(jwest<0)) westvalid=true; if (adjacencymatrix[i][j]==-1){ //if vertex unvisited adjacencymatrix[i][j]=0; //mark vertex visited ij ij = new ij(i,j); orderofvisits.add(ij); //add vertex visit list system.out.println("visit i,j: " + +" " +j); double lottery = math.random(); (int rows=i; rows<m; rows++) (int cols=j; cols<n; cols++){ if (lottery>0.75d){ if(northvalid) { dfs(inorth,j); } if(southvalid){ dfs(isouth,j); } if(eastvalid){ dfs(i, jeast); } if(westvalid){ dfs(i,jwest); } } else if (lottery<0.25d) { if(westvalid){ dfs(i,jwest); } if(eastvalid){ dfs(i, jeast); } if(southvalid){ dfs(isouth,j); } if(northvalid) { dfs(inorth,j); } } else if ((lottery>=0.25d)&&(lottery<0.5d)) { if(southvalid){ dfs(isouth,j); } if(eastvalid){ dfs(i, jeast); } if(westvalid){ dfs(i,jwest); } if(northvalid){ dfs(inorth,j); } } else if ((lottery>=0.5d)&&(lottery<=0.75d)) { if(eastvalid){ dfs(i, jeast); } if(westvalid){ dfs(i,jwest); } if(southvalid){ dfs(isouth,j); } if(northvalid){ dfs(inorth,j); } } } } //end nested } //end dfs // } public class main { /** * @param args command line arguments */ public static void main(string[] args) { // todo code application logic here graph thegraph = new graph(3,3); thegraph.dfs_i(0, 0); // thegraph.dfs(0,0); } }
same issue in other post
ij (int i,int j){ //i = this.i; //j= this.j; this.i = i; this.j = j; visited=false; } 
Comments
Post a Comment