{"id":571,"date":"2024-10-10T13:42:27","date_gmt":"2024-10-10T08:12:27","guid":{"rendered":"https:\/\/codexplained.in\/?p=571"},"modified":"2025-11-24T15:56:36","modified_gmt":"2025-11-24T10:26:36","slug":"check-bipartite-graph","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=571","title":{"rendered":"Verification of Bipartite Graph"},"content":{"rendered":"
\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\nint graph[MAX][MAX];  \/\/ Adjacency matrix to represent the graph\nint color[MAX];       \/\/ Array to store colors assigned to vertices\nint n;                \/\/ Number of vertices\n\n\/\/ Function to perform DFS and check bipartiteness\nint isBipartiteUtil(int node, int c) {\n    color[node] = c;  \/\/ Assign color to the current node\n\n    \/\/ Explore all adjacent vertices\n    for (int i = 0; i < n; i++) {\n        \/\/ If there is an edge and the adjacent vertex is uncolored\n        if (graph[node][i]) {\n            if (color[i] == -1) {\n                \/\/ Recursive DFS call with alternate color\n                if (!isBipartiteUtil(i, 1 - c)) {\n                    return 0;  \/\/ Not bipartite\n                }\n            } else if (color[i] == c) {\n                return 0;  \/\/ Not bipartite if the same color is found\n            }\n        }\n    }\n    return 1;  \/\/ Successfully colored\n}\n\n\/\/ Function to check if the graph is bipartite\nint isBipartite() {\n    \/\/ Initialize color array with -1 (indicating no color assigned)\n    for (int i = 0; i < n; i++) {\n        color[i] = -1;\n    }\n\n    \/\/ Check each component of the graph\n    for (int i = 0; i < n; i++) {\n        if (color[i] == -1) {  \/\/ If not colored\n            if (!isBipartiteUtil(i, 0)) {\n                return 0;  \/\/ Not bipartite\n            }\n        }\n    }\n    return 1;  \/\/ Graph is bipartite\n}\n\nint main() {\n    printf("Enter number of vertices: ");\n    scanf("%d", &n);\n\n    printf("Enter adjacency matrix (0\/1):\\n");\n    for (int i = 0; i < n; i++)\n        for (int j = 0; j < n; j++)\n            scanf("%d", &graph[i][j]);\n\n    if (isBipartite()) {\n        printf("The graph is bipartite.\\n");\n    } else {\n        printf("The graph is not bipartite.\\n");\n    }\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
Explanation of the Code<\/h3>\n\n\n\n
    \n
  1. Data Structures<\/strong>:\n
      \n
    • graph[MAX][MAX]<\/code>: This is an adjacency matrix where graph[i][j]<\/code> is 1<\/code> if there is an edge between vertex i<\/code> and vertex j<\/code>, and 0<\/code> otherwise.<\/li>\n\n\n\n
    • color[MAX]<\/code>: This array stores the color assigned to each vertex. It\u2019s initialized to -1<\/code> to indicate that no color has been assigned yet.<\/li>\n\n\n\n
    • n<\/code>: This variable holds the number of vertices in the graph.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • Function isBipartiteUtil<\/code><\/strong>:\n
        \n
      • This is a recursive function that attempts to color the graph. It takes a node<\/code> and the current color c<\/code>.<\/li>\n\n\n\n
      • It assigns the color to the current node and recursively colors its adjacent nodes with the alternate color (0 becomes 1 and vice versa).<\/li>\n\n\n\n
      • If it finds a conflict (an adjacent node has the same color), it returns 0<\/code>, indicating that the graph is not bipartite.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
      • Function isBipartite<\/code><\/strong>:\n
          \n
        • It initializes the color<\/code> array.<\/li>\n\n\n\n
        • It checks each vertex; if it\u2019s uncolored, it calls isBipartiteUtil<\/code>. If any component is found to be non-bipartite, it returns 0<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Main Function<\/strong>:\n
            \n
          • It prompts the user for the number of vertices and the adjacency matrix.<\/li>\n\n\n\n
          • It then calls the isBipartite<\/code> function and prints whether the graph is bipartite.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
            Sample Input and Output<\/h3>\n\n\n\n
            Input:<\/h4>\n\n\n\n
            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<\/code>
             
            output:<\/strong>
            The graph is bipartite.
            <\/pre>\n