I need the following code to check if the graph is a bipartite graph or not using the BFS algorithm. But i am getting errors with two parts in the code. One is the print parent and the other is the BFS check itself. Following is my code.

/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */

/** * * @author Owner */

import java.util.LinkedList; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.List; import java.util.Queue; public class Graph { List> adjList = null;

private static class Vertex { LinkedList adj; // adjacency list int color; // color assigned to vertex int parent; // parent in bfs forest/tree boolean visited; // already visited or not ? // ADD/MODIFY AS YOU SEE FIT // constructor Vertex() { adj = new LinkedList (); parent = -1; visited = false; // ADD/MODIFY AS YOU SEE FIT } // add neighbor w void addNeighbor (int w) { adj.addLast(w); } } private int nVertices; // number of vertices; vertices are 1 .. nVertices private Vertex[] vertices; // array of vertices; [0] not used // ADD/MODIFY AS YOU SEE FIT // Vertices are labeled 1 through n; hence any array allocated // has n+1 components with component [0] not used public Graph (int n) { nVertices = n; vertices = new Vertex[n+1]; // only [1] through [n] will be used // construct the vertices for (int v = 1; v <= nVertices; v++) vertices[v] = new Vertex(); } // add the edge v-w public void addEdge (int v, int w) { vertices[v].addNeighbor(w); vertices[w].addNeighbor(v); } // end of addEdge // print the adjacency lists of vertices to the given // printwriter public void printAdjacencies (PrintWriter output) { int v; output.println ("Adjacency lists of graph:"); for(int i=1; i<=nVertices;i++){ output.print("Vertice "+ i + ": "); output.println(vertices[i].adj); } // COMPLETE THE CODE } // end of prinAdjacencies // print parent of each vertex in BFS tree to given printwriter public void printParents (PrintWriter output) { int v; output.println("Parents in DFS tree:"); output.printf ("Vertex: "); for (v = 1; v <= nVertices; v++) output.printf ("%2d ", v); output.println(); output.printf("Parent: "); for (v = 1; v <= nVertices; v++) output.printf ("%2d ", vertices[v].parent); output.println(); }// end of printParents // Pre: graph is connected, has at least one edge, and list is valid // Return value: true if graph is bipartite and false otherwise // Post: previous value of list is lost // graph remains unchanged // if graph is bipartite, list has vertices of color 1, followed // by 0, followed by vertices of color 2 // otherwise, list has vertices of an odd cycle in cyclic order // Uses: BFS // Complexity: O(m+n) public boolean bipartite (Graph graph, int v, int N) { //LinkedList list // COMPLETE THE CODE

// Vertex.visited == Boolean Visit Switch // stores level of each vertex in BFS // stores vertex is discovered or not boolean[] discovered = new boolean[N]; int[] level = new int[N];

// mark source vertex as discovered and // set its level to 0 discovered[v] = true; level[v] = 0;

// create a queue to do BFS and enqueue // source vertex in it Queue q = new ArrayDeque<>(); q.add(v);

// run till queue is not empty while (!q.isEmpty()) { // pop front node from queue and print it v = q.poll();

// do for every edge (v -> u) for (int u : graph.adjList.get(v)) { // if vertex u is explored for first time if (!discovered[u]) { // mark it discovered discovered[u] = true;

// set level as level of parent node + 1 level[u] = level[v] + 1;

// push the vertex into the queue q.add(u); } // if the vertex is already been discovered and // level of vertex u and v are same, then the // graph contains an odd-cycle & is not biparte else if (level[v] == level[u]) return false; } } return true; } // end of bipartite } // end of class Graph

Your help is much appreciated!