Java Coding Test Course, Determining Bipartite Graphs

This article will cover the concept of ‘bipartite graph’ and an algorithm problem for determining it. A bipartite graph is a graph where the vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Such graphs can be applied to various problems and play a crucial role in algorithms like bipartite matching.

1. Problem Definition

Here is an example of the problem of determining a bipartite graph:


Problem: Determine if a graph is bipartite.

Input: 
- The first line contains the number of vertices N and the number of edges M. (1 ≤ N, M ≤ 100,000)
- The next M lines contain two vertices u and v for each edge. (1 ≤ u, v ≤ N)

Output:
- Print "Yes" if it is a bipartite graph, otherwise print "No".

2. What is a Bipartite Graph?

A bipartite graph is a graph structure that allows the vertices to be divided under specific conditions. That is, if any two vertices u and v are connected by an edge, then u and v must belong to different sets. Due to this property, bipartite graphs can be colored with two colors. In other words, all vertices belonging to one set are colored the same, while vertices in the other set are colored differently.

3. Algorithm Approach

The method for determining a bipartite graph is as follows. The graph is explored using DFS (Depth First Search) or BFS (Breadth First Search), coloring each vertex during the process.

  1. Represent the graph using an adjacency list.
  2. If there are unvisited vertices, start BFS or DFS from that vertex.
  3. Assign a color to the starting vertex and assign a different color to its adjacent vertices while exploring.
  4. If an adjacent vertex has already been visited and has the same color, it determines that it is not a bipartite graph.
  5. After exploring all vertices, determine whether it is a bipartite graph and print the result.

4. Java Code Implementation

Below is the Java code implemented based on the above algorithm:


import java.util.*;

public class BipartiteGraph {
    static List> graph;
    static int[] color;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        color = new int[N + 1];
        boolean isBipartite = true;
        
        for (int i = 1; i <= N; i++) {
            if (color[i] == 0) {
                if (!bfs(i)) {
                    isBipartite = false;
                    break;
                }
            }
        }
        
        System.out.println(isBipartite ? "Yes" : "No");
    }
    
    private static boolean bfs(int start) {
        Queue queue = new LinkedList<>();
        queue.offer(start);
        color[start] = 1; // Color the starting vertex
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (color[neighbor] == 0) {
                    // If the adjacent vertex has not been visited
                    color[neighbor] = 3 - color[node]; // Color it differently
                    queue.offer(neighbor);
                } else if (color[neighbor] == color[node]) {
                    // If the adjacent vertex has the same color
                    return false;
                }
            }
        }
        return true;
    }
}

5. Code Explanation

The above Java code implements an algorithm for determining a bipartite graph. Let’s examine each part in detail.

5.1 Graph Representation

The graph is represented as an adjacency list in the form of List>. It stores the list of each vertex and adds edge information to complete the graph structure.

5.2 Color Array

The color array color manages the colors of each vertex. 0 indicates not visited, and 1 and 2 represent two different colors.

5.3 BFS Exploration

The bfs method uses the BFS algorithm to explore the graph. It adds the starting vertex to the queue and colors the visited vertices. Then it assigns colors to adjacent vertices and checks for conflicts. If a vertex with the same color is found, the graph is not a bipartite graph.

6. Time Complexity

The time complexity of this algorithm is O(N + M). Here, N denotes the number of vertices and M denotes the number of edges. This is because all vertices and edges of the graph are explored once.

7. Other Considerations

This algorithm can handle both connected and disconnected graphs. In the case of a disconnected graph, each component is independently checked to determine if it is bipartite.

8. Conclusion

This article addressed the problem of determining a bipartite graph. Such problems are frequently encountered and are particularly useful for algorithm interview preparation. Understanding bipartite graphs will help solve various graph-related problems in the future. Continuous practice and solving a diverse range of problems are recommended to enhance coding skills.