Determine Whether an Undirected Graph Is Two-Colorable

Question

The candidate is asked to determine if a given undirected graph can be colored using two colors such that no two adjacent vertices share the same color.

Codemia · Accepted Answer

To determine whether an undirected graph is two-colorable, we need to check if we can color the graph using two colors without any two adjacent vertices sharing the same color. This is equivalent to checking if the graph is bipartite.

We can use either a Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph. The idea is to start from any vertex, assign it a color, and then color all its adjacent vertices with the opposite color. If we ever find an adjacent vertex that has the same color as the current vertex, the graph is not two-colorable.

Here is a Python implementation using BFS:

```python
from collections import deque

def is_bipartite(graph):
    color = {}
    for node in graph:
        if node not in color:
            queue = deque([node])
            color[node] = 0  # Start coloring with 0
            while queue:
                current = queue.popleft()
                for neighbor in graph[current]:
                    if neighbor not in color:
                        color[neighbor] = 1 - color[current]
                        queue.append(neighbor)
                    elif color[neighbor] == color[current]:
                        return False
    return True
```
This code initializes a color dictionary to track the colors assigned to each vertex and uses a queue for BFS traversal.

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This is because we visit each vertex and edge once. The space complexity is O(V) due to the storage of the color dictionary.

We should consider edge cases such as an empty graph, a graph with a single vertex, or a graph with disconnected components. The algorithm should handle these cases gracefully, returning True for an empty graph and checking each component in a disconnected graph.

Determine Whether an Undirected Graph Is Two-Colorable

Apple

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Apple Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string