javaalgorithmbreadth-first-searchclrs

Implementing Breadth First Search from CLRS in Java


At my wits end here. I'm following this psuedocode from CLRS and I don't know why my final for loop doesn't keep going to give me the distance from the given source node to all other vertices. I'm so lost that I don't know which part of this I'm messing up. The way our assignment is, we get skeleton code that differs slightly and we have to find a way to augment our code to make it work. I think I've done so mostly but I think I'm using the wrong variables in the wrong places. Sorry that I'm not explaining it better but again, I don't know what part here is messing up.

package graph;

import ds.Queue;
import java.util.*;

public class Graph {
    public int n;   //number of vertice
    public int[][] A;   //the adjacency matrix
    private final int WHITE = 2;
    private final int GRAY = 3;
    private final int BLACK = 4;
    
    public Graph () {
        n = 0;
        A = null;
    }
    
    public Graph (int _n, int[][] _A) {
        this.n = _n;
        this.A = _A;
    }
    
    /*
     * Input: s denotes the index of the source node
     * Output: the array dist, where dist[i] is the distance between the i-th node to s
     */
    public int[] bfs (int s) 
    {
        int [] dist = new int[n];
        int [] col = new int[n];
        for (int i = 0; i < n; i++)
        {
            col[i] = WHITE;
            dist[i] = Integer.MAX_VALUE;
        }
        col[s] = GRAY;
        dist[s] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.add(s);

        while (!q.isEmpty())
        {
            int u = q.poll();

            for (int i : A[u])
            {
                if(col[i] == WHITE)
                {
                    col[i] = GRAY;
                    dist[i] = dist[u] + 1;
                    q.add(i);
                }
            }
            col[u] = BLACK;
        }
        return dist;



    }
    
    public void print_array (int[] array) {
        for (int i = 0; i < array.length; i++)
            System.out.println(i + ": " + array[i]);
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n = 8;
        int[][] A = 
            {{0, 1, 0, 0, 1, 0, 0, 0},
            {1, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 0, 1, 0, 1, 1, 0},
            {0, 0, 1, 0, 0, 0, 1, 1},
            {1, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 0, 0, 0, 1, 0},
            {0, 0, 1, 1, 0, 1, 0, 1},
            {0, 0, 0, 1, 0, 0, 1, 0}};
        Graph g = new Graph(n, A);
        g.print_array(g.bfs(1));
    }

}

pseudo code


Solution

  • You are given a graph represented as an adjacency matrix, not an adjacency list, so to find the neighbors of a node i, iterate over all other nodes j and check if A[i][j] is 1.

    for (int v = 0; v < n; v++)
        if (A[u][v] == 1 && col[v] == WHITE) {
            col[v] = GRAY;
            dist[v] = dist[u] + 1;
            q.add(v);
        }