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));
}
}
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);
}