Bipartite Graph Check in DSA Go

Mental Model

A bipartite graph can be split into two groups where no nodes inside the same group connect to each other.

Analogy: Imagine two teams playing a game where players only pass the ball to the other team, never to their own teammates.

Group A: 1 -> 3 -> 5
Group B: 2 -> 4 -> 6
Edges only go between groups, never inside one group.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1

Goal: Check if the graph can be colored using two colors so that no connected nodes share the same color.

Step 1: Start coloring node 1 with color 0

1[0], 2[uncolored], 3[uncolored], 4[uncolored]

Why: We pick a starting node and assign the first color.

Step 2: Color neighbors of 1 (node 2 and 4) with color 1

1[0] -> 2[1], 4[1], 3[uncolored]

Why: Neighbors must have opposite color to avoid same-group edges.

Step 3: Color neighbor of 2 (node 3) with color 0

1[0], 2[1] -> 3[0], 4[1]

Why: Neighbors of color 1 get color 0.

Step 4: Check neighbors of 3 (nodes 2 and 4). Node 4 is color 1, no conflict.

1[0], 2[1], 3[0], 4[1]

Why: No two connected nodes share the same color, so far so good.

Step 5: Check neighbors of 4 (nodes 1 and 3). Both colors differ, no conflict.

1[0], 2[1], 3[0], 4[1]

Why: All edges connect nodes of different colors, confirming bipartite.

Result:

1[0] -> 2[1] -> 3[0] -> 4[1]
Graph is bipartite: true

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// Graph represents an undirected graph using adjacency list
type Graph struct {
	adj map[int][]int
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

// AddEdge adds an undirected edge between u and v
func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

// isBipartite checks if the graph is bipartite using DFS coloring
func (g *Graph) isBipartite() bool {
	color := make(map[int]int) // node to color mapping
	const UNCOLORED = -1

	// Initialize all nodes as uncolored
	for node := range g.adj {
		color[node] = UNCOLORED
	}

	var dfs func(int, int) bool
	dfs = func(node, c int) bool {
		color[node] = c // assign color to current node

		for _, neighbor := range g.adj[node] {
			if color[neighbor] == UNCOLORED {
				if !dfs(neighbor, 1-c) { // color neighbor with opposite color
					return false
				}
			} else if color[neighbor] == c {
				return false // neighbor has same color, not bipartite
			}
		}
		return true
	}

	// Check all components
	for node := range g.adj {
		if color[node] == UNCOLORED {
			if !dfs(node, 0) {
				return false
			}
		}
	}
	return true
}

func main() {
	g := NewGraph()
	// Add edges: 1-2, 2-3, 3-4, 4-1
	g.AddEdge(1, 2)
	g.AddEdge(2, 3)
	g.AddEdge(3, 4)
	g.AddEdge(4, 1)

	result := g.isBipartite()
	fmt.Printf("1[0] -> 2[1] -> 3[0] -> 4[1]\nGraph is bipartite: %v\n", result)
}

color[node] = c // assign color to current node

assign current node the given color

for _, neighbor := range g.adj[node] {

iterate over all neighbors of current node

if color[neighbor] == UNCOLORED {

if neighbor is not colored, color with opposite color recursively

if !dfs(neighbor, 1-c) {

if coloring neighbor fails, graph is not bipartite

} else if color[neighbor] == c {

if neighbor has same color, graph is not bipartite

for node := range g.adj {

check all nodes to handle disconnected components

if color[node] == UNCOLORED {

start DFS coloring from uncolored nodes

Output

1[0] -> 2[1] -> 3[0] -> 4[1]

Graph is bipartite: true

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during DFS

Space: O(V) for storing colors and recursion stack in worst case

vs Alternative: Compared to BFS approach, DFS is similar in complexity but uses recursion; naive checking all pairs would be O(V^2)

Edge Cases

Empty graph

Returns true since no edges violate bipartite property

DSA Go

for node := range g.adj {

Graph with single node and no edges

Returns true as single node can be colored any color

DSA Go

for node := range g.adj {

Graph with odd cycle (e.g., triangle 1-2-3-1)

Returns false because odd cycle cannot be bipartite

DSA Go

else if color[neighbor] == c {

When to Use This Pattern

When a problem asks if a graph can be split into two groups with no internal edges, use bipartite check with graph coloring to verify.

Common Mistakes

Mistake: Not checking all disconnected components in the graph
Fix: Run DFS/BFS coloring from every uncolored node to cover all components

Mistake: Assigning the same color to neighbors instead of opposite color
Fix: Always assign neighbors the opposite color (1 - current color)

Summary

Checks if a graph can be divided into two groups with no edges inside the same group.

Use when you need to verify if a graph is bipartite or can be 2-colored.

The key insight is to color nodes alternately and detect conflicts to confirm bipartiteness.

Practice

1. What does it mean for a graph to be bipartite?

easy

A. It has an equal number of vertices and edges

B. All vertices have the same degree

C. It contains at least one cycle

D. Its vertices can be divided into two sets with no edges inside the same set

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph is one where vertices can be split into two groups so that no edge connects vertices within the same group.

2. Step 2: Compare options with definition

   Its vertices can be divided into two sets with no edges inside the same set matches this definition exactly, while others describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two sets with no edges inside the same set -> Option D

4. Quick Check:

   Bipartite graph = Two sets, no internal edges [OK]

Hint: Bipartite means two groups with no edges inside each group [OK]

Common Mistakes:

• Confusing bipartite with equal vertices and edges
• Thinking bipartite means having cycles
• Assuming all vertices have same degree

2. Which Go data structure is best to represent a graph for bipartite check?

easy

A. map[int][]int

B. []int

C. map[int]int

D. [][]int

Solution

1. Step 1: Identify graph representation needs

   We need to store each vertex and its connected vertices (neighbors).

2. Step 2: Match data structures to graph representation

   map[int][]int maps each vertex to a list of neighbors, perfect for adjacency list representation.

3. Final Answer:

   map[int][]int -> Option A

4. Quick Check:

   Adjacency list = map[int][]int [OK]

Hint: Use map[int][]int for adjacency list in Go [OK]

Common Mistakes:

• Using []int which is just a list, not graph
• Using map[int]int which maps to single int, not neighbors
• Using [][]int without clear vertex indexing

3. What will be the output of this Go code snippet checking bipartite for graph with edges: 0-1, 1-2, 2-3, 3-0?

graph := map[int][]int{
  0: {1, 3},
  1: {0, 2},
  2: {1, 3},
  3: {2, 0},
}
result := isBipartite(graph)
fmt.Println(result)

Assuming isBipartite returns true if graph is bipartite, false otherwise.

medium

A. false

B. Compilation error

C. true

D. Runtime panic

Solution

1. Step 1: Analyze the graph structure

   The graph forms a cycle of length 4: 0-1-2-3-0.

2. Step 2: Check bipartite condition for even cycle

   Even length cycles are bipartite, but here edges connect 0-3 and 2-3, making it a 4-cycle which is bipartite. However, 0-3 edge closes the cycle.

3. Step 3: Re-examine edges

   Edges are 0-1,1-2,2-3,3-0 forming a square (4-cycle). This is bipartite, so isBipartite should return true.

4. Final Answer:

   false -> Option A

5. Quick Check:

   Even cycle graph is bipartite = false [Incorrect]

Hint: Even length cycles are bipartite, odd are not [OK]

Common Mistakes:

• Thinking all cycles are not bipartite
• Confusing edge directions
• Assuming runtime errors without code errors

4. Identify the bug in this Go function snippet for bipartite check:

func isBipartite(graph map[int][]int) bool {
  color := make(map[int]int)
  var dfs func(int, int) bool
  dfs = func(node, c int) bool {
    if val, ok := color[node]; ok {
      return val == c
    }
    color[node] = c
    for _, nei := range graph[node] {
      if !dfs(nei, 1-c) {
        return false
      }
    }
    return true
  }
  for node := range graph {
    if _, ok := color[node]; !ok {
      if !dfs(node, 0) {
        return false
      }
    }
  }
  return true
}

medium

A. Missing initialization of color map

B. Incorrect color flipping logic in dfs call

C. No bug, function correctly checks bipartite

D. DFS function does not return any value

Solution

1. Step 1: Review color map initialization

   color map is initialized properly with make(map[int]int).

2. Step 2: Check DFS logic and color flipping

   DFS flips color with 1-c correctly and returns false if conflict found.

3. Step 3: Confirm DFS returns and main loop

   DFS returns bool, main loop calls DFS on uncolored nodes, returns false if conflict.

4. Final Answer:

   No bug, function correctly checks bipartite -> Option C

5. Quick Check:

   DFS with color flipping and map works correctly [OK]

Hint: Check color flip and return values in DFS [OK]

Common Mistakes:

• Forgetting to flip color with 1-c
• Not returning DFS results properly
• Not initializing color map

5. Given a graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-3, 3-4, 4-5, 5-0, 1-4. Is this graph bipartite?

hard

A. No, because it has disconnected components

B. Yes, because it has no odd cycles

C. Yes, because all vertices can be colored the same

D. No, because it contains an odd cycle

Solution

1. Step 1: Analyze the graph structure

   The graph is a cycle 0-1-2-3-4-5-0 of length 6 (even) with an additional edge 1-4.

2. Step 2: Check for odd-length cycles

   Check cycles involving the extra edge 1-4: cycle 1-4-5-0-1 has length 4 (even), but cycle 1-2-3-4-1 is length 4 (even). However, the presence of edge 1-4 creates a triangle 1-4-5-0-1? Actually, no triangle. But check carefully: 1-4-5-0-1 is length 4, no odd cycle. But 1-4-5-0-1 is 4 edges, so even. So no odd cycle. So graph is bipartite.

3. Final Answer:

   Yes, because it has no odd cycles -> Option B

4. Quick Check:

   No odd cycles = bipartite [OK]

Hint: Odd cycles mean graph is not bipartite [OK]

Common Mistakes:

• Thinking the extra edge 1-4 creates an odd cycle
• Assuming all cycles are even without checking
• Confusing disconnected with bipartite