Sponsored
Sponsored
This approach uses breadth-first search (BFS) to try and color the graph using two colors, validating its bipartiteness. By starting at any unvisited node and attempting to color it with one color, you color all its neighbors with an alternating color. If at any point a neighbor is found to already have the same color, then the graph cannot be bipartite.
The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each edge and vertex is visited once in BFS. The space complexity is O(V) due to the storage needed for the color array and the BFS queue.
1import java.util.*;
2
3public class BipartiteCheck {
4 public boolean bfsCheck(int node, int[][] graph, int[] colors) {
5 Queue<Integer> queue = new LinkedList<>();
6 queue.add(node);
7 colors[node] = 0;
8
9 while (!queue.isEmpty()) {
10 int u = queue.poll();
11 for (int v : graph[u]) {
12 if (colors[v] == -1) {
13 colors[v] = 1 - colors[u];
14 queue.add(v);
15 } else if (colors[v] == colors[u]) {
16 return false;
17 }
18 }
19 }
20 return true;
21 }
22
23 public boolean isBipartite(int[][] graph) {
24 int n = graph.length;
25 int[] colors = new int[n];
26 Arrays.fill(colors, -1);
27
28 for (int i = 0; i < n; i++) {
29 if (colors[i] == -1) {
30 if (!bfsCheck(i, graph, colors)) {
31 return false;
32 }
33 }
34 }
35 return true;
36 }
37
38 public static void main(String[] args) {
39 BipartiteCheck check = new BipartiteCheck();
40 int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
41 System.out.println(check.isBipartite(graph));
42 }
43}This Java implementation utilizes a class BipartiteCheck with methods to execute BFS and color nodes with two colors. The bfsCheck method ensures that all neighbors of a node get an opposite color, rejecting any configuration where a conflict is detected. The adjacency list is implemented as a 2D array.
The depth-first search (DFS) approach is an alternative to BFS for examining bipartiteness. You use DFS recursively to color the graph and check for conflicts. The method still involves checking whether adjacent nodes have opposing colors, iterating through components one by one as needed.
The time complexity is O(V + E), and the space complexity is O(V) due to recursive depth stack space utilization.
1#
In this C implementation, the dfsCheck function initiates a depth-first recursive coloring, verifying that no adjacent nodes share the same color. Each time a recursive call finds a color conflict, it will return false, propagating back through the recusrsion stack to the caller.