#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int graph[MAX][MAX]; // Adjacency matrix to represent the graph
int color[MAX]; // Array to store colors assigned to vertices
int n; // Number of vertices
// Function to perform DFS and check bipartiteness
int isBipartiteUtil(int node, int c) {
color[node] = c; // Assign color to the current node
// Explore all adjacent vertices
for (int i = 0; i < n; i++) {
// If there is an edge and the adjacent vertex is uncolored
if (graph[node][i]) {
if (color[i] == -1) {
// Recursive DFS call with alternate color
if (!isBipartiteUtil(i, 1 - c)) {
return 0; // Not bipartite
}
} else if (color[i] == c) {
return 0; // Not bipartite if the same color is found
}
}
}
return 1; // Successfully colored
}
// Function to check if the graph is bipartite
int isBipartite() {
// Initialize color array with -1 (indicating no color assigned)
for (int i = 0; i < n; i++) {
color[i] = -1;
}
// Check each component of the graph
for (int i = 0; i < n; i++) {
if (color[i] == -1) { // If not colored
if (!isBipartiteUtil(i, 0)) {
return 0; // Not bipartite
}
}
}
return 1; // Graph is bipartite
}
int main() {
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (0/1):\n");
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &graph[i][j]);
if (isBipartite()) {
printf("The graph is bipartite.\n");
} else {
printf("The graph is not bipartite.\n");
}
return 0;
}
Explanation of the Code
Data Structures:
graph[MAX][MAX]: This is an adjacency matrix where graph[i][j] is 1 if there is an edge between vertex i and vertex j, and 0 otherwise.
color[MAX]: This array stores the color assigned to each vertex. It’s initialized to -1 to indicate that no color has been assigned yet.
n: This variable holds the number of vertices in the graph.
Function isBipartiteUtil:
This is a recursive function that attempts to color the graph. It takes a node and the current color c.
It assigns the color to the current node and recursively colors its adjacent nodes with the alternate color (0 becomes 1 and vice versa).
If it finds a conflict (an adjacent node has the same color), it returns 0, indicating that the graph is not bipartite.
Function isBipartite:
It initializes the color array.
It checks each vertex; if it’s uncolored, it calls isBipartiteUtil. If any component is found to be non-bipartite, it returns 0.
Main Function:
It prompts the user for the number of vertices and the adjacency matrix.
It then calls the isBipartite function and prints whether the graph is bipartite.
Sample Input and Output
Input:
Mathematica Copy code Enter number of vertices: 4 Enter adjacency matrix (0/1): 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
