CODEWITHSUNDEEP
javadepth-first-search
Frederico Schardong
Frederico Schardong

Reputation: 2095

Another depth first search in java issue

I am tying to implement a depth first search algorithm in java to find the best way to move in a quadratic matrix. I am avoiding to create "unnecessary" objects, i.e object just to hold (X,Y) positions.

Am I forgetting something? I am running it with starting points of (0,0) and with objective of (4,5). What happens is an infinite loop.

int x = this.move_to_x;
int y = this.move_to_y;

Stack X = new Stack();
Stack Y = new Stack();

Stack visited_X = new Stack();
Stack visited_Y = new Stack();

X.push(this.current_x);
Y.push(this.current_y);

while(!X.empty()){
    int tmp_x = (int)X.pop();
    int tmp_y = (int)Y.pop();

    if(tmp_x == x && tmp_y == y){
        System.out.println("best way found!");
        return;
    }

    //there is only 8 possible ways to go (the neighbors)
    for(int a = -1; a < 2; a++){
        for(int b = -1; b < 2; b++){
            if(a == 0 && b == 0){
                break;
            }

            if(visited_X.search(tmp_x + a) == -1 && visited_Y.search(tmp_y + b) == -1){
                X.push(tmp_x + a);
                Y.push(tmp_y + b);

                visited_X.push(tmp_x + a);
                visited_Y.push(tmp_y + b);

                System.out.println("added x " + tmp_x + a + " y " + tmp_y + b);
            }
        }
    }
}

Upvotes: 1

Views: 173

Answers (1)

NPE
NPE

Reputation: 500167

I can see several problems:

1) In the following:

        if(a == 0 && b == 0){
            break;
        }

you should be using continue rather than break.

2) The following:

if(visited_X.search(tmp_x + a) == -1 && visited_Y.search(tmp_y + b) == -1){

is incorrect: the (tmp_x, tmp_y) pair has to be present at the same index in visited_X/visited_Y.

3) You should add the starting position to visited_{X,Y}.

4) Algorithmically, I don't see any reason to think that your method would return the shortest path.

5) The reason your code ends up in (an almost) infinite loop is that you don't check for the matrix boundaries.

Upvotes: 1

Related Questions