C++ Coding Test Course, Bipartite Graph Checking

Hello! Today we will learn about bipartite graphs. A bipartite graph is a graph in which the set of vertices can be divided into two subsets, and there are no edges between vertices within the same subset. This topic is one of the frequently posed questions in coding tests. In the next session, we will explore the algorithms and coding needed to determine if a graph is bipartite.

Problem Description

The problem is to determine whether the given undirected graph is bipartite. Starting from a vertex, we need to check whether we can visit all vertices while satisfying the bipartite graph conditions.

Problem Example

Given the following graph, determine whether it is a bipartite graph.

Vertices: 6
Edges: 
1 - 2
1 - 3
2 - 4
2 - 5
3 - 6

Looking at the graph above, we can see if it can be divided into two sets. Set A is {1, 4, 5, 6} and Set B is {2, 3}. This graph is indeed a bipartite graph.

Problem Solving Strategy

One method we can use to confirm if a graph is bipartite is Breadth-First Search (BFS) or Depth-First Search (DFS). Both methods can be employed to traverse the graph while coloring each vertex (or grouping them) to verify the bipartite graph conditions.

Algorithm Steps

1. Represent the graph in the form of an adjacency list.
2. Run a loop to visit all nodes.
3. Color the current vertex to divide it into two groups.
4. Check if adjacent vertices have the same color.
5. Repeat until all nodes have been visited or until all reachable nodes are visited.

C++ Code Implementation

Let’s take a look at the C++ code to determine if this undirected graph is bipartite.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 1000; // Maximum number of vertices
vector<int> graph[MAX];
int color[MAX]; // Color setting: -1 is unvisited, 0 and 1 are groups

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0; // Color the starting vertex

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int neighbor : graph[v]) {
            // If the neighboring vertex has not been visited, color it.
            if (color[neighbor] == -1) {
                color[neighbor] = 1 - color[v]; // Assign a different color than the current vertex
                q.push(neighbor);
            }
            // If the neighboring vertex has the same color as the current vertex, it is not a bipartite graph.
            else if (color[neighbor] == color[v]) {
                return false; // Violates the bipartite graph conditions
            }
        }
    }
    return true;
}

int main() {
    int v, e;
    cout << "Enter the number of vertices and edges: ";
    cin >> v >> e;

    // Initialize the graph
    for (int i = 0; i < MAX; i++) {
        color[i] = -1;
    }

    cout << "Input edges (format: a b): " << endl;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); // Undirected graph
    }

    bool result = true;
    for (int i = 1; i <= v; i++) {
        if (color[i] == -1) {
            // If this vertex is unvisited, check if it is bipartite
            if (!isBipartite(i)) {
                result = false;
                break;
            }
        }
    }

    if (result) {
        cout << "This graph is a bipartite graph." << endl;
    } else {
        cout << "This graph is not a bipartite graph." << endl;
    }

    return 0;
}

Code Explanation

This code takes the vertices and edges of the given graph as input and determines whether the graph is bipartite. The isBipartite function checks if all adjacent vertices are of different colors.

Variable and Structure Explanation

• graph[MAX]: Adjacency list representation of the graph.
• color[MAX]: An array representing the color of each vertex.
• queue<int> q: The queue used for BFS.

Input Example and Output Result

When running the code, an example of inputting edges is as follows.

Enter the number of vertices and edges: 6 5
Input edges (format: a b): 
1 2
1 3
2 4
2 5
3 6

When given the above input, the output will be as follows.

This graph is a bipartite graph.

Conclusion

In conclusion, we learned how to determine if a graph is bipartite using C++. Understanding the basic principle of solving problems using BFS or DFS can be applied to various graph problems. I hope this helps your preparation for coding tests!