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.
1using System;
2using System.Collections.Generic;
3
4public class BipartiteGraph {
5 public bool BfsCheck(int start, int[][] graph, int[] colors) {
6 Queue<int> queue = new Queue<int>();
7 queue.Enqueue(start);
8 colors[start] = 0;
9
10 while (queue.Count > 0) {
11 int u = queue.Dequeue();
12 foreach (int v in graph[u]) {
13 if (colors[v] == -1) {
14 colors[v] = 1 - colors[u];
15 queue.Enqueue(v);
16 } else if (colors[v] == colors[u]) {
17 return false;
18 }
19 }
20 }
21 return true;
22 }
23
24 public bool IsBipartite(int[][] graph) {
25 int n = graph.Length;
26 int[] colors = new int[n];
27 Array.Fill(colors, -1);
28
29 for (int i = 0; i < n; i++) {
30 if (colors[i] == -1) {
31 if (!BfsCheck(i, graph, colors)) {
32 return false;
33 }
34 }
35 }
36 return true;
37 }
38
39 public static void Main() {
40 BipartiteGraph bg = new BipartiteGraph();
41 int[][] graph = new int[][] {
42 new int[] {1, 3}, new int[] {0, 2},
43 new int[] {1, 3}, new int[] {0, 2}
44 };
45 Console.WriteLine(bg.IsBipartite(graph));
46 }
47}The C# implementation uses a Queue to traverse the graph and color nodes as in previous examples. The method BfsCheck is called for each partially explored component of the graph, helping spot any inconsistencies in the simple two-color attempt to verify bipartiteness.
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.
1using System;
public class BipartiteGraphDFS {
public bool DfsCheck(int node, int color, int[][] graph, int[] colors) {
colors[node] = color;
foreach (int neighbor in graph[node]) {
if (colors[neighbor] == -1) {
if (!DfsCheck(neighbor, 1 - color, graph, colors)) return false;
} else if (colors[neighbor] == colors[node]) {
return false;
}
}
return true;
}
public bool IsBipartite(int[][] graph) {
int n = graph.Length;
int[] colors = new int[n];
Array.Fill(colors, -1);
for (int i = 0; i < n; i++) {
if (colors[i] == -1) {
if (!DfsCheck(i, 0, graph, colors)) {
return false;
}
}
}
return true;
}
public static void Main() {
BipartiteGraphDFS bg = new BipartiteGraphDFS();
int[][] graph = new int[][] {
new int[] {1, 3}, new int[] {0, 2},
new int[] {1, 3}, new int[] {0, 2}
};
Console.WriteLine(bg.IsBipartite(graph));
}
}In C#, DFS implemented with recursion checks each node and recurses with opposite coloring, which upon failure returns a false condition back through the method calls, terminating at its invocation point in IsBipartite when a mismatch is confirmed.