Please use the pseudocode above!

You are provided one skeleton program named Graph.java

Please modify the skeleton code to solve the following tasks.

Task 1: .Implement the bfs(int s) function:

Note: You should return an integer array that records the minimum distance between every node to the sources.

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 represent 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, use

your previous implementation of Queue in HW3. Or you can use the add() and remove()

function of Java LinkedList.

Task 2 (Extra Credit 100 pts). Implement the DFS() and DFS Visit() function.

----------------------------------------------------------------

Here's skeleton code

-------------------------------------------------------------------

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) {

----code goes here!----

}

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

}

}

Breadth-First Search BFS(G,s) 1 for each vertex u e G.V - {s) For each node v, u.colorWHITE u.d =00 u. = NIL 4 5 s.color=GRAY 6 s.d=0 7 s.=NIL v.d: the minimum distance to s v.Tt: the parent of v to reach s v.color: WHITE: v has not been discovered yet GRAY: v has been discovered, but not its neighbo Black: v and its neighbors have been discovered. 9 ENQUEUE(Q,s) 10 while 0 u = DEQUEUE(Q) for each v E G.Adj[u] It will not be visited any more. 12 13 if v. color == WHITE v,color = GRAY 15 16 17 ENQUEUE(Q, v) 18 ucolor = BLACK Breadth-First Search BFS(G,s) 1 for each vertex u e G.V - {s) For each node v, u.colorWHITE u.d =00 u. = NIL 4 5 s.color=GRAY 6 s.d=0 7 s.=NIL v.d: the minimum distance to s v.Tt: the parent of v to reach s v.color: WHITE: v has not been discovered yet GRAY: v has been discovered, but not its neighbo Black: v and its neighbors have been discovered. 9 ENQUEUE(Q,s) 10 while 0 u = DEQUEUE(Q) for each v E G.Adj[u] It will not be visited any more. 12 13 if v. color == WHITE v,color = GRAY 15 16 17 ENQUEUE(Q, v) 18 ucolor = BLACK