Possible Bipartition Problem in Java
The Bipartition problem in graph theory entails allocating colors to the vertices of an undirected graph so that adjacent vertices have different colors. The goal is to see if it is possible to partition the vertices into two disjoint sets, each with its own color, so that every edge connects a vertex of one color to a vertex of the other. If such a coloring is possible, the graph is called bipartite; otherwise, it is not.
Example 1:
Input:
Output: The graph is bipartite.
Explanation: An octagon can be bipartite if its vertices are arranged in two sets with no two adjacent vertices within the same set connected by an edge. For example, you can color alternate vertices orange and green, resulting in two distinct sets.
Example 2:
Input:
Output: The graph is not bipartite.
Explanation: A triangle (three vertices) cannot be bipartite. Regardless of how you color the vertices, at least one edge will connect two vertices of the same color, which violates the notion of a bipartite network.
Approach: Using BFS
Step 1: The original graph, which has V vertices, is represented by an adjacency list (adjList). Simultaneously, the vertex colors are stored in a colors array that is initialized at -1.
Step 2: To add undirected edges between vertices, use the addEdge() function.
Step 3: For each uncolored vertex (colors[i] == -1), initiate a breadth-first search (BFS) traversal using the isBipartiteUtil() method. Assign the color 1 to the source vertex and apply BFS coloring in the isBipartiteUtil() method. During traversal, look for conflicts and return false if any are discovered.
Step 4: Return true to signify that the graph is bipartite if the BFS traversal is finished for every vertex without encountering any conflicts. To show that the graph is not bipartite, return false if a conflict arises during traversal.
FileName: Bipartition.java
import java.util.*;
public class Bipartition {
private int V;
private List<List<Integer>> adjList;
public Bipartition(int v) {
V = v;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; ++i)
adjList.add(new ArrayList<>());
}
void addEdge(int v, int w) {
adjList.get(v - 1).add(w - 1);
adjList.get(w - 1).add(v - 1);
}
boolean isBipartite() {
int[] colors = new int[V];
Arrays.fill(colors, -1);
for (int i = 0; i < V; ++i) {
if (colors[i] == -1 && !isBipartiteUtil(i, colors))
return false;
}
return true;
}
boolean isBipartiteUtil(int src, int[] colors) {
colors[src] = 1;
LinkedList<Integer> queue = new LinkedList<>();
queue.add(src);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adjList.get(u)) {
if (colors[v] == -1) {
colors[v] = 1 - colors[u];
queue.add(v);
} else if (colors[v] == colors[u]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
Bipartition g = new Bipartition(8);
// Adding edges to represent the cycle of an octagon
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 7);
g.addEdge(7, 8);
g.addEdge(8, 1);
if (g.isBipartite())
System.out.println("The graph is bipartite.");
else
System.out.println("The graph is not bipartite.");
}
}
Output:
The graph is bipartite.
Complexity Analysis: The time complexity of bipartite verification using BFS is O(V + E), where V is the number of vertices and E is the number of edges. It searches each vertex and edge once, resulting in a linear graph size. The queue has a space complexity of O(V).
Approach: Using DFS
The Java code defines a class called Bipartition1 to determine whether an undirected graph is bipartite or not. The graph is represented as an adjacency list. It employs a depth-first search (DFS) strategy to assign colors (0 or 1) to vertices in such a way that no two neighboring vertices share the same color. The isBipartite() function sets colors and iterates through all vertices, calling isBipartiteUtil() on each uncolored vertex. The isBipartiteUtil() method iteratively searches neighbors, looking for any neighboring vertices with the same color.
FileName: Bipartition1.java
import java.util.*;
public class Bipartition1 {
private int V;
private List<List<Integer>> adjList;
public Bipartition1(int v) {
V = v;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; ++i)
adjList.add(new ArrayList<>());
}
void addEdge(int v, int w) {
adjList.get(v - 1).add(w - 1);
adjList.get(w - 1).add(v - 1);
}
boolean isBipartite() {
int[] colors = new int[V];
Arrays.fill(colors, -1);
for (int i = 0; i < V; ++i) {
if (colors[i] == -1 && !isBipartiteUtil(i, colors, 0))
return false;
}
return true;
}
boolean isBipartiteUtil(int src, int[] colors, int color) {
colors[src] = color;
for (int v : adjList.get(src)) {
if (colors[v] == -1) {
if (!isBipartiteUtil(v, colors, 1 - color))
return false;
} else if (colors[v] == colors[src]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Bipartition1 g = new Bipartition1(8);
// Adding edges to represent the cycle of an octagon
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 7);
g.addEdge(7, 8);
g.addEdge(8, 1);
if (g.isBipartite())
System.out.println("The graph is bipartite.");
else
System.out.println("The graph is not bipartite.");
}
}
Output:
The graph is bipartite.
Complexity Analysis: DFS for bipartite verification has a time complexity of O(V + E), which means it visits each vertex and edge once. The recursive call stack or explicit stack has a space complexity of O(V), which makes it memory efficient.
Approach: Using XOR-Based Coloring
The Java program includes a Bipartition2 class, which provides methods for determining whether an undirected graph is bipartite. The class has a constructor Bipartition() for initializing the graph, an addEdge() method for adding edges, and the isBipartite() method, which uses an XOR-based color assignment during DFS traversal. The isBipartiteUtil() method assigns colors recursively while checking for conflicts.
FileName: Bipartition2.java
import java.util.*;
public class Bipartition2 {
private int V;
private List<List<Integer>> adjList;
public Bipartition2(int v) {
V = v;
adjList = new ArrayList<>(V);
for (int i = 0; i < V; ++i)
adjList.add(new ArrayList<>());
}
void addEdge(int v, int w) {
adjList.get(v - 1).add(w - 1);
adjList.get(w - 1).add(v - 1);
}
boolean isBipartite() {
int[] colors = new int[V];
Arrays.fill(colors, -1);
for (int i = 0; i < V; ++i) {
if (colors[i] == -1 && !isBipartiteUtil(i, colors, 0))
return false;
}
return true;
}
boolean isBipartiteUtil(int src, int[] colors, int color) {
colors[src] = color;
for (int v : adjList.get(src)) {
if (colors[v] == -1) {
if (!isBipartiteUtil(v, colors, color ^ 1))
return false;
} else if ((colors[v] ^ colors[src]) == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Bipartition2 g = new Bipartition2(8);
// Adding edges to represent the cycle of an octagon
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.addEdge(5, 6);
g.addEdge(6, 7);
g.addEdge(7, 8);
g.addEdge(8, 1);
if (g.isBipartite())
System.out.println("The graph is bipartite.");
else
System.out.println("The graph is not bipartite.");
}
}
Output:
The graph is bipartite.
Complexity Analysis: The XOR-based coloring approach for bipartite verification has a time and space complexity of O(V + E), which is consistent with the efficiency of traditional BFS and DFS approaches. It uses bitwise XOR operations to assign colors during graph traversal.