CODEWITHSUNDEEP
algorithmgraph-algorithmbreadth-first-search
Thomas
Thomas

Reputation: 103

What's wrong with my Breadth First Search Algorithm

I am taking an algorithm course and we are currently working on graphs. I am calculating the minimum distance between two nodes. I implemented a breadth first search algorithm to accomplish this. It works with the test cases thee course gives. But the automated grader still fails on one of the tests. They don't display the input or output for these tests. Could someone take a look at this and tell me what I'm doing wrong?

import java.awt.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BFS {
static int[] dist;
static Stack<Integer> stack = new Stack<Integer>();
private static int distance(ArrayList<Integer>[] adj, int s, int t) {
    dist= new int[adj.length];

    for(int i=0; i<dist.length;i++){
        dist[i]=Integer.MAX_VALUE;
    }
    dist[s]=0;
    stack.push(s);


    while(!stack.empty()){
        int u= stack.pop();
        for(int v: adj[u]){
            if(dist[v]==Integer.MAX_VALUE){
                stack.push(v);
                dist[v]=dist[u]+1;

            }

        }

    }
    if(dist[t]!=Integer.MAX_VALUE){
        return dist[t];
    }
    return -1;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int m = scanner.nextInt();
    ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[n];
    for (int i = 0; i < n; i++) {
        adj[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        x = scanner.nextInt();
        y = scanner.nextInt();
        adj[x - 1].add(y - 1);
        adj[y - 1].add(x - 1);
    }
    int x = scanner.nextInt() - 1;
    int y = scanner.nextInt() - 1;
    System.out.println(distance(adj, x, y));
}
}

Thanks in advance.

Upvotes: 1

Views: 115

Answers (1)

Mathias Rav
Mathias Rav

Reputation: 2973

You appear to have implemented depth-first search (with a stack) rather than breadth-first search (with a queue). Your implementation fails on the following example:

5 5
1 2
2 5
1 3
3 4
4 5
1 5

The distance between node 1 and 5 is 2, as witnessed by the path 1-2-5. However, your implementation finds only the path 1-3-4-5 (of length 3) since it visits the edges in the following order:

1-2 (distance 1)
1-3 (distance 1)
3-4 (distance 2)
4-5 (distance 3)
2-5 (no-op since 5 is already visited)

Upvotes: 2

Related Questions