package graph;

import ds.Queue;

public class Graph {

public int n; /umber 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) {

}

public void print_array (int[] array) {

for (int i = 0; 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));

}

}

Task 1 (100 pts). Implement the bfs(int s) function as discussed in Lecture 15. Note: You should return an integer array that records the mini- mum distance between every node to the source s. Hint 1: The colors have been defined in the class for you to use. Hint 2: In the matrix-adjacency representation, each node is just an integer. So you cannot do this u, color = WHITE for a node u. Instead, I suggest you to create an integer array to rep- resent the colors of the nodes, another array to represent the distance d for the nodes Hint 3: You can ignore the parent in your code. Hint 4: To use the Enqueue and Dequeue function, you may use your previous implementation of Queue in HW3. Or you can use the add) and remove() function of Java LinkedList (https://docs. oracle.com/javase/7/docs/api/java/util/LinkedList.html). More tutorials can be found https://www.javatpoint.com/java-linkedlist and http://www.javadb.com/using-a-queue-or-linkedlist/