Check if a Graph is Bipartite

Bipartite graphs are a fundamental concept in graph theory with widespread applications in various fields. A graph is considered bipartite if its nodes can be divided into two disjoint sets, say ‘U’ and ‘V’, such that every edge connects a node in ‘U’ to a node in ‘V’ (and no edges exist within ‘U’ or ‘V’). This post explores how to efficiently determine if a given graph is bipartite using Python.

Understanding Bipartite Graphs

Before diving into the code, let’s solidify our understanding. A simple example of a bipartite graph is a graph representing relationships between students and the courses they are enrolled in. Students form one set (U), courses form another (V), and edges represent enrollment. Conversely, a graph representing friendships within a group is unlikely to be bipartite, as friendships can exist between any two individuals.

Python Implementation using Breadth-First Search (BFS)

BFS offers an elegant approach to check for bipartiteness. The algorithm assigns colors (e.g., 0 and 1) to nodes as it explores the graph. If a node’s neighbor has the same color, the graph is not bipartite.

from collections import deque

def is_bipartite(graph):
    """
    Checks if a graph is bipartite using Breadth-First Search (BFS).

    Args:
        graph: A dictionary representing the graph where keys are nodes and values are lists of their neighbors.

    Returns:
        True if the graph is bipartite, False otherwise.
    """
    num_nodes = len(graph)
    colors = [-1] * num_nodes  # -1 indicates uncolored, 0 and 1 represent colors

    for node in range(num_nodes):
        if colors[node] == -1:
            queue = deque([node])
            colors[node] = 0  # Assign initial color

            while queue:
                curr_node = queue.popleft()
                for neighbor in graph[curr_node]:
                    if colors[neighbor] == -1:
                        colors[neighbor] = 1 - colors[curr_node] # Assign opposite color
                        queue.append(neighbor)
                    elif colors[neighbor] == colors[curr_node]:
                        return False  # Conflict: Not bipartite

    return True  # All nodes colored without conflict


# Example graph represented as an adjacency list
graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 3],
    3: [0, 2]
}

if is_bipartite(graph):
    print("The graph is bipartite.")
else:
    print("The graph is not bipartite.")


#Example of a non-bipartite graph
graph2 = {
    0: [1,2],
    1: [0,2],
    2: [0,1]
}

if is_bipartite(graph2):
    print("The graph is bipartite.")
else:
    print("The graph is not bipartite.")

This code efficiently uses BFS to traverse the graph and detect any color conflicts, providing a clear and concise solution to the bipartite graph checking problem. The use of a collections.deque ensures optimal performance for queue operations.

Alternative Approach: Depth-First Search (DFS)

While BFS is often preferred for its simplicity, Depth-First Search can also be adapted to determine bipartiteness. The core logic remains the same: assign colors and check for conflicts during traversal. The difference lies primarily in the exploration strategy (breadth-first vs. depth-first). Implementing DFS for this task is left as an exercise for the reader, as the underlying principle is very similar to the BFS approach. The choice between BFS and DFS often depends on specific performance needs and graph characteristics.