BFS/Queue

package bfs;

import stack_queue_linkedlist.Queue;

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 [] color = new int[n];
        int [] distance =  new int[n];
        Queue queue = new Queue(n);
        int u = 0;


        for(int i=0; i<n; i++) {
            if(i!=s) {
                color[i]=WHITE;
                distance[i]=Integer.MAX_VALUE;
            }
        }
        color[s]=GRAY;
        distance[s]=0;

        queue.enqueue(s);

        while (queue != null) {
            System.out.println(queue);

            u = queue.dequeue();


            for(int v=0;v<n;v++) {
                if (color[v]==WHITE && A[u][v]==1) {
                    color[v]=GRAY;
                    distance[v] = distance[u]+1;
                    queue.enqueue(v);
                }

            }
            color[u] = BLACK;
        }


        return distance;
    }

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

}




//QUEUE CLASS
/*****************************************************************
 *
 * CSIT212 - Queue.java     Justin Trubela      10/12/21
 *
 * Purpose: Queue
 *
 * Task 2 (30 pts.).   Implement  the enqueue(int x), dequeue()
 *      function forQueue in Queue.java as discussed in Lecture 5.
 * Task 5 (10 pts. Extra Credit). In the enqueue(int x) function of
 *      Queue.java,we do not check if the queue is already full.
 *      Implement the capacity check feature for enqueue(int x) to
 *      print  the error message.)
 * Task 6 (10 pts Extra Credit).  In the dequeue()function of
 *      Queue.java,we do not check if the queue is empty.
 *      If we dequeue an empty queue,we should also get an error.
 *      Implement the empty check feature for enqueue(int x).
 *
 *****************************************************************/


package stack_queue_linkedlist;

public class Queue {

    public int size;
    public int[] array;
    public int head;
    public int tail;

    public Queue () {
        size = 0;
        array = null;
        head = 0;
        tail = 0;
    }

    public Queue (int _size) {
        size = _size;
        array = new int[size];
        head = 0;
        tail = 0;
    }

    /*
     * Implement the ENQUEUE(Q, x) function
     */
    public void enqueue (int x) {

            array[tail] = x;

            if (array.length==0) {
                tail = 1;
            }

            if (tail == array.length-1) {
                System.err.println("Queue is full already");
            }
            else {
                tail++;
            }

    }

    /*
     * Implement the DEQUEUE(Q) function
     */

    public int dequeue () {
        int x = array[head];

        if (head > tail||head < 0) {
            System.err.println("Queue is empty already");
            return x;
        }
        else {
            head++;
        }
        return x;
    }


    /*
     * Convert queue to string in the format of #size, head, tail, [#elements]
     */
    public String toString () {
        String str;

        str = size + ", " + head + ", " + tail + ", [";
        for (int i = head; i%size < tail; i++)
            str += array[i] + ",";

        str += "]";
        return str;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Queue q;

        q = new Queue(10);
        for (int i = 0; i < 5; i++)
            q.enqueue(i);
        System.out.println(q.toString());
        for (int i = 0; i < 7; i++)
            q.dequeue();
        System.out.println(q.toString());
    }

}