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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <string.h>
4
5bool bfsCheck(int node, int graph[][100], int graphSize, int* graphColSize, int* color) {
6 int queue[100], front = 0, rear = 0;
7 queue[rear++] = node;
8 color[node] = 0;
9
10 while (front < rear) {
11 int u = queue[front++];
12 for (int i = 0; i < graphColSize[u]; i++) {
13 int v = graph[u][i];
14 if (color[v] == -1) { // If not colored, color with opposite color
15 color[v] = 1 - color[u];
16 queue[rear++] = v;
17 } else if (color[v] == color[u]) {
18 return false;
19 }
20 }
21 }
22 return true;
23}
24
25bool isBipartite(int graph[][100], int graphSize, int* graphColSize) {
26 int color[100];
27 memset(color, -1, sizeof(color));
28
29 for (int i = 0; i < graphSize; i++) {
30 if (color[i] == -1) {
31 if (!bfsCheck(i, graph, graphSize, graphColSize, color)) {
32 return false;
33 }
34 }
35 }
36 return true;
37}
38
39int main() {
40 int graph[4][100] = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
41 int graphSize = 4;
42 int graphColSize[] = {2, 2, 2, 2};
43 printf("%s\n", isBipartite(graph, graphSize, graphColSize) ? "true" : "false");
44 return 0;
45}This implementation uses a function bfsCheck to perform a BFS from a specific node, attempting to color nodes with two colors. The visited nodes are stored in a queue, and adjacent nodes get an alternating color. The function immediately returns false if any adjacent nodes have the same color, indicating a non-bipartite graph.
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.
1def
In Python, the recursive DFS function dfsCheck checks for coloring conflicts via backtracking as it explores the graph. It responds effectively to earlier function stack calls when an adjacency invalidates a previous assumption.