C# Coding Test Course, Determine Bipartite Graph

1. Introduction

Graph theory is an important area in computer science and algorithms, utilized to solve various real-world problems.
In this article, we will introduce the concept of ‘bipartite graphs’ and the algorithmic problem of determining them,
detailing how to solve it using C#. A bipartite graph is one in which the vertices of the graph are divided into two sets,
ensuring that no two vertices within the same set are connected. Such graphs play a significant role in various applications.
For example, they are frequently used to represent connections between two different types of objects or in bipartite matching problems.

2. Problem Description

In this problem, you are required to implement an algorithm to determine whether a given graph is a bipartite graph.
For instance, the number of vertices V and the number of edges E are provided, along with
V vertices and E edges connecting them. If the given graph is a bipartite graph, you should output “YES”; otherwise, output “NO”.

Input Format

        The first line contains the number of vertices V and the number of edges E. 
        The next E lines contain two integers representing the endpoints of each edge.

Output Format

        If the given graph is a bipartite graph, output "YES"; otherwise, output "NO".

3. Algorithmic Approach

To solve this problem, we will use either BFS (Breadth-First Search) or DFS (Depth-First Search).
The method we will employ for determining whether a graph is bipartite involves coloring each vertex with two different colors.
Specifically, one set will be marked with color 1 and the other with color 2. If two adjacent vertices are colored the same, it indicates that the graph is not bipartite.

Algorithm Steps

  1. Create a data structure to represent the graph in an adjacency list format.
  2. Visit the vertices using BFS or DFS and determine the colors of the vertices.
  3. Check if adjacent vertices have the same color to determine bipartiteness.
  4. After visiting all vertices, output the final result.

4. C# Code Implementation

Now, based on the described algorithm, we will implement the code in C#.
Below is the C# code for determining whether a graph is bipartite. 

using System;
using System.Collections.Generic;

class Program
{
    static List[] graph;
    static int[] color;

    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int V = int.Parse(input[0]);
        int E = int.Parse(input[1]);

        graph = new List[V + 1];
        for (int i = 0; i <= V; i++)
            graph[i] = new List();

        for (int i = 0; i < E; i++)
        {
            input = Console.ReadLine().Split();
            int u = int.Parse(input[0]);
            int v = int.Parse(input[1]);
            graph[u].Add(v);
            graph[v].Add(u);
        }

        color = new int[V + 1];

        bool isBipartite = true;
        for (int i = 1; i <= V; i++)
        {
            if (color[i] == 0)
                isBipartite &= BFS(i);
        }

        Console.WriteLine(isBipartite ? "YES" : "NO");
    }

    static bool BFS(int start)
    {
        Queue queue = new Queue();
        queue.Enqueue(start);
        color[start] = 1;  // Color the starting vertex

        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node])
            {
                if (color[neighbor] == 0)  // If not colored yet
                {
                    color[neighbor] = 3 - color[node];  // Color with different color
                    queue.Enqueue(neighbor);
                }
                else if (color[neighbor] == color[node])  // If the adjacent vertices have the same color
                {
                    return false;
                }
            }
        }
        return true;
    }
}

5. Code Explanation

I will explain the key components and logic used in the C# code above.

Data Structures

– List[] graph: Used to represent the graph in an adjacency list format.
It stores the list of connected vertices using the vertex numbers as keys.

– int[] color: Stores the colors of each vertex. 0 indicates uncolored, while 1 and 2 represent the two different colors.

Main Method

– Receives the number of vertices and edges as input, based on which the graph is constructed.

– Iterates through all vertices, calling BFS to check if the graph is bipartite.
After checking all given vertices, the result is printed.

BFS Method

– The BFS method performs breadth-first search using a queue.
It colors the starting vertex and colors adjacent vertices with a different color if they are not colored yet.

– If an already colored vertex is found to be colored the same as the current vertex, it returns false, indicating that the graph is not bipartite.

6. Complexity Analysis

The time complexity of this algorithm is O(V + E).
Here, V is the number of vertices and E is the number of edges, as the algorithm explores all vertices and edges of the graph.
Thus, it can operate efficiently given the input size.

7. Conclusion

This article explained the definition of bipartite graphs and how to solve the problem of determining them using C#.
I hope it helped in understanding the basics of graph theory and the BFS/DFS algorithms, enabling practical applications.
Moreover, I encourage you to enhance your understanding of graph algorithms by solving various problems.

8. Additional References