CODEWITHSUNDEEP
javaalgorithmdata-structurestreebreadth-first-search
zackmusgrave
zackmusgrave

Reputation: 53

Connectivity of a graph in java

I've implemented a BFS algorithm from my textbook and I am trying to modify it to throw an exception when it discovers a non-connected graph. My BFS using an array of boolean to store if a node has been reached or not. After running the BFS from the root node I thought I could iterate through the array and check if each node was reached. My code throws an exception every time and I cannot figure out why. Any guidance would be appreciated thanks!

Code:

private int bfs(Graph G, int s) {
    int d = 0;
    Queue<Integer> q = new Queue<>();
    int distTo[] = new int[G.V()], max = 0;
    boolean[] marked = new boolean[G.V()];
    int[] edgeTo = new int[G.V()];
    for(int v = 0; v < G.V(); v++) {
        distTo[s] = Integer.MAX_VALUE;
        marked[s] = true;
        distTo[s] = 0;
        q.enqueue(s);
    }
    
    while(!q.isEmpty()) {
        d = q.dequeue();
        for(int w : G.adj(d)) {
            if(!marked[w]) {
                edgeTo[w] = d;
                distTo[w] = distTo[d] + 1;
                marked[w] = true;
                q.enqueue(w);
            }
        }
        for(boolean x : marked) {
            if(x == false) throw new RuntimeException("not a connected graph.");
        }
    }
    return d;
}

Upvotes: 0

Views: 138

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

You check for connectivity after processing each vertex. Only in the simplest graphs will the test succeed after the first vertex.

Instead you should seed the queue with one vertex and move the for loop testing for connectivity out of the while loop.

Upvotes: 1

Related Questions