write a java program for the following question: A graph is bipartite if its ver
ID: 3588500 • Letter: W
Question
write a java program for the following question:
A graph is bipartite if its vertices can be divided into two disjoint sets such that no edges exist between vertices in the same set (see sets U and V in the figure below) Add a new method in AbstractGraph with the following header to return two bipartite sets if the graph is bipartite: public List getBipartite The method returns a List that contains two sublists, each of which contains a set of vertices. If the graph is not bipartite, the method returns nul1.An ArrayList is an appropriate List.Explanation / Answer
// program for checking given graph is Bipartite or not
import java.util.*;
import java.lang.*;
import java.io.*;
class Bpartite
{
final static int V = 4; // No. of Vertices
// This function returns true if graph G[V][V] is Bipartite, else false
boolean isBpartite(int G[][],int src)
{
// Create a color array to store colors assigned to all veritces.
// Vertex number is used as index in this array. The value '-1'
// of colorGraph[i] is used to indicate that no color is assigned
// to vertex 'i'. The value 1 is used to indicate first color
// is assigned and value 0 indicates second color is assigned.
int colorGraph[] = new int[V];
for (int i=0; i<V; ++i)
colorGraph[i] = -1;
// Assign first color to source
colorGraph[src] = 1;
// Create a queue (FIFO) of vertex numbers and enqueue
// source vertex for BFS traversal
LinkedList<Integer>q = new LinkedList<Integer>();
q.add(src);
// Run while there are vertices in queue (Similar to BFS)
while (q.size() != 0)
{
// Dequeue a vertex from queue
int u = q.poll();
// Return false if there is a self-loop
if (G[u][u] == 1)
return false;
// Find all non-colored adjacent vertices
for (int v=0; v<V; ++v)
{
// An edge from u to v exists and destination v is
// not colored
if (G[u][v]==1 && colorGraph[v]==-1)
{
// Assign alternate color to this adjacent v of u
colorGraph[v] = 1-colorGraph[u];
q.add(v);
}
// An edge from u to v exists and destination v is
// colored with same color as u
else if (G[u][v]==1 && colorGraph[v]==colorGraph[u])
return false;
}
}
// If we reach here, then all adjacent vertices can
// be colored with alternate color
System.out.println("Set1 of Bipartite graph");
for (int i=0; i<V; i=i+2)
System.out.println("Vertex -"+i+", color = "+colorGraph[i]);
System.out.println("Set2 of Bipartite graph");
for (int i=1; i<V; i=i+2)
System.out.println("Vertex -"+i+", color = "+colorGraph[i]);
return true;
}
// Driver program to test above function
public static void main (String[] args)
{
int Graph[][] = {
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 0, 1, 0}
};
Bpartite b = new Bpartite();
if (b.isBpartite(Graph, 0))
System.out.println("Given graph is Bipartite");
else
System.out.println("Given graph is not Bipartite");
}
}
Output :
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.