Write a program that checks if a graph is bipartite.
- User
Write a program that checks if a graph is bipartite.
Assistant
The user wants a program to check if a graph is bipartite.
1. Understand the concept of a Bipartite Graph:
- A graph is bipartite if its vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in .
- Equivalently, a graph is bipartite if and only if it is 2-colorable (e.g., can be colored with two colors such that no adjacent nodes share the same color).
- Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.
2. Choose the Algorithm: The most common and efficient way to check for bipartiteness is using Breadth-First Search (BFS) or Depth-First Search (DFS).
- Algorithm (BFS approach):
- Assign a color (say, 1) to the source node.
- Assign the opposite color (say, -1) to all its neighbors.
- Repeat recursively (iteratively using a queue) for all neighbors.
- If we encounter a node that is already colored and has the same color as its neighbor, the graph is not bipartite.
- Since the graph might be disconnected, we need to run this check for every unvisited component.
3. Select the Programming Language: Python is generally the most accessible language for algorithmic examples due to its readability. I should probably provide a Python solution, but maybe offer C++ or Java as well if requested. Since the prompt is generic ("Write a program"), Python is the safest default choice. I will write the solution in Python.
4. Draft the Code Structure (Python):
- Input: An adjacency list representing the graph. Let's say
graphis a dictionary or a list of lists wheregraph[u]contains neighbors ofu. - Data Structure: An array or dictionary
colorsto store the state of each node (-1, 0, 1). 0 means uncolored/visited. 1 and -1 are the two colors. - Function:
is_bipartite(graph)
5. Refine the Code Logic:
def is_bipartite(graph): n = len(graph) # Number of nodes colors = [0] * n # 0: uncolored, 1: color A, -1: color B # Iterate through all nodes to handle disconnected components for i in range(n): if colors[i] != 0: continue # Already visited # Start BFS queue = [i] colors[i] = 1 # Assign first color while queue: curr = queue.pop(0) for neighbor in graph[curr]: if colors[neighbor] == 0: # Color with opposite color colors[neighbor] = -colors[curr] queue.append(neighbor) elif colors[neighbor] == colors[curr]: # Same color neighbor -> Not bipartite return False return True6. Handling Input Formats: The user didn't specify the input format.
- Format A (Adjacency List):
[[1,3], [0,2], [1,3], [0,2]] - Format B (Edge List):
[(0,1), (1,2), ...] - Format C (Adjacency Matrix):
[[0,1...], [1,0...]]
I will stick to the Adjacency List as it's the standard for graph traversal problems. I'll provide a complete runnable example including a main block to demonstrate usage.
7. Edge Cases:
- Empty graph: Trivially bipartite. The loop range(0) won't run, returns True.
- Single node: Bipartite. Colors[0] becomes 1, queue empty, returns True.
- Disconnected graph: The outer loop handles this.
8. Alternative Implementation (DFS): DFS is often cleaner to write recursively, but iterative BFS is easier to explain conceptually for "layers" of coloring. I'll stick with BFS but maybe mention DFS works too. Actually, let's stick to BFS as the primary solution because checking cycles usually implies level-order logic in tutorials.
9. Constructing the Explanation:
- Define what Bipartite means (2-colorable).
- Explain the BFS approach.
- Provide the code.
- Explain the code logic (initialization, outer loop for components, inner loop for traversal, conflict check).
- Provide example inputs (one bipartite, one not).
10. Refining the Code for "Production" Quality:
- Use
collections.dequefor efficient popping from the front in Python. - Add comments.
- Make the graph size explicit.
Let's write the actual response.
- Language: Python 3.
- Approach: BFS 2-coloring.
- Code:
- Define
is_bipartite(n, edges)oris_bipartite(graph). Let's assume the input is an adjacency list for simplicity, or provide a conversion. Providing the adjacency list directly is best for algorithmic clarity.
- Define
Let's double check the logic for a simple triangle (0-1, 1-2, 2-0).
- Start 0 -> color 1. Queue: [0]
- Pop 0. Neighbors 1, 2.
- Neighbor 1 -> color -1. Queue: [1]
- Neighbor 2 -> color -1. Queue: [1, 2]
- Pop 1. Neighbors 0, 2.
- Neighbor 0 is color 1. 1 != -1. OK.
- Neighbor 2 is color -1. -1 == -1. Conflict! Return False.
- Correct.
Logic for a line (0-1, 1-2).
- Start 0 -> color 1. Queue: [0]
- Pop 0. Neighbor 1.
- Neighbor 1 -> color -1. Queue: [1]
- Pop 1. Neighbors 0, 2.
- Neighbor 0 color 1 != -1.
- Neighbor 2 uncolored -> color 1. Queue: [2]
- Pop 2. Neighbor 1 color -1 != 1.
- Queue empty. Return True. Correct.
Final Output Structure:
- Brief explanation of the logic (BFS + 2 colors).
- Python Code.
- Example usage.
- Time/Space complexity analysis.
I should also consider writing it in C++ or Java just in case, but usually, one language is sufficient unless specified. I will provide Python as the primary answer.
Wait, what if the graph input is just edges? I will assume the input is an Adjacency List because it's the most efficient representation for this algorithm.
Let's add a small note about the input format.
Code:
from collections import deque def is_bipartite(graph): """ Checks if a graph is bipartite using BFS (Breadth-First Search). A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other. """ n = len(graph) # 0: Uncolored, 1: Red, -1: Blue colors = [0] * n # Loop through all nodes to handle disconnected graphs for i in range(n): if colors[i] != 0: continue # Start BFS queue = deque([i]) colors[i] = 1 # Assign first color while queue: node = queue.popleft() for neighbor in graph[node]: if colors[neighbor] == 0: # If neighbor is not colored, color with opposite color colors[neighbor] = -colors[node] queue.append(neighbor) elif colors[neighbor] == colors[node]: # If neighbor has same color, graph is not bipartite return False return TrueThis looks solid. I will format this nicely.
One small detail: Should I support an adjacency matrix? No, usually "graph" implies adjacency list in competitive programming/interview contexts unless specified. I'll stick to the list.
Complexity: Time: O(V + E) - standard BFS. Space: O(V) - for color array and queue.
I'll write the response now. Here is a Python program to check if a graph is bipartite.
The Logic
A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other.
The standard way to check this is using Breadth-First Search (BFS) (or DFS) to try and 2-color the graph:
- Assign a color (e.g., Red/1) to the source node.
- Assign the opposite color (e.g., Blue/-1) to all its neighbors.
- Repeat for all neighbors.
- If you encounter an edge that connects two nodes of the same color, the graph is not bipartite.
- If you finish coloring without conflicts, the graph is bipartite.
The Code (Python)
from collections import deque def is_bipartite(graph): """ Checks if a graph is bipartite using BFS. Args: graph (dict or list): Adjacency list representation of the graph. Example: {0: [1, 3], 1: [0, 2], ...} Returns: bool: True if bipartite, False otherwise. """ # Determine the number of nodes. # Handles both dictionary input {0:[...], 1:[...]} and list of lists [[...], [...]] if isinstance(graph, dict): nodes = list(graph.keys()) else: nodes = range(len(graph)) # Dictionary to store colors. # 1 = Group A, -1 = Group B, None = Uncolored colors = {node: None for node in nodes} # We iterate through all nodes because the graph might be disconnected for start_node in nodes: # If the node is already colored, we've processed its component if colors[start_node] is not None: continue # Start BFS for this component queue = deque([start_node]) colors[start_node] = 1 # Assign initial color while queue: current = queue.popleft() for neighbor in graph[current]: # If neighbor is not colored, color it opposite to current if colors[neighbor] is None: colors[neighbor] = -colors[current] queue.append(neighbor) # If neighbor has the SAME color as current, conflict found! elif colors[neighbor] == colors[current]: return False return True # --- Usage Examples --- if __name__ == "__main__": # Example 1: A Bipartite Graph (Square 0-1-2-3-0) # 0 -- 1 # | | # 3 -- 2 bipartite_graph = { 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2] } # Example 2: A Non-Bipartite Graph (Triangle 0-1-2-0) # Odd cycles are never bipartite non_bipartite_graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1] } print(f"Graph 1 is bipartite: {is_bipartite(bipartite_graph)}") # Output: True print(f"Graph 2 is bipartite: {is_bipartite(non_bipartite_graph)}") # Output: FalseComplexity Analysis
- Time Complexity: , where is the number of vertices and is the number of edges. We visit every node and every edge exactly once.
- Space Complexity: , to store the
colorsdictionary and the BFS queue.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.