Pranav Kasetti

What is a Bipartite Graph?

Bipartite graphs are graphs where the edges are only between the corresponding vertices of 2 distinct sets. A graph with no vertices is Bipartite, and a graph with more than one connected component can be Bipartite.

Problem Statement

Detect whether a given graph is Bipartite in O(n) time and using max O(m+n) space where m is the number of edges and the number of vertices is n.

Algorithm Description

1. Convert the edge list to an adjacency list.
2. Initialise an array of visited vertices and an array of colors of each vertex. Unvisited vertices are stored as false, and visited vertices as true. Store the colors of each vertex as 0 for set 1, and 1 for set 2.
3. Modify DFS/BFS by updating the color of unvisited neighbour nodes when traversing to the opposite color of the parent. When we encounter a neighbour that we've already visited, check if the neighbour has the same color as the current parent. Since we chose the color before, we can't change the color. In this case, we've detected a cycle and the graph cannot be bipartite.
4. Wrapper function calling DFS/BFS for every connected component, and return false if any DFS/BFS returns not Bipartite.

Wrapper function (Swift)

func isBipartite(_ edges: [(Int, Int)], _ n: Int) -> Bool {
  var adjList: [[Int]] = Array(repeating: [], count: n)
  
  for (src, dst) in edges {
    adjList[src].append(dst)
    adjList[dst].append(src)
  }
  
  var visited = Array(repeating: false, count: n)
  var color = Array(repeating: -1, count: n)
  
  func dfs(_ start: Int) -> Bool { ... }
  
  for i in 0 ..< n {
    if !visited[i] {
      color[i] = 0
      if !dfs(i) {
        return false
      }
    }
  }
  
  return true
}

DFS with Bipartite Modifications (Swift)

func dfs(_ start: Int) -> Bool {
  visited[start] = true
  for neighbour in adjList[start] {
    if !visited[neighbour] {
      color[neighbour] = 1 - color[start]
      if !dfs(neighbour) {
        return false
      }
    } else if color[neighbour] == color[start] {
      return false
    }
  }
  return true
}

BFS with Bipartite Modifications (Swift)

We can replace the DFS function above with a modified BFS traversal.

func bfs(_ start: Int) -> Bool {
  visited[start] = true
  color[start] = 0
  var queue = [start]
  while !queue.isEmpty {
    let curr = queue.removeFirst()
    for neighbour in adjList[curr] {
      if !visited[neighbour] {
        visited[neighbour] = true
        color[neighbour] = 1 - color[curr]
        queue.append(neighbour)
      } else if color[neighbour] == color[curr] {
        return false
      }
    }
  }
  return true
}

Choices Made

1. I've used a Visited Array instead of a HashMap. The choice doesn't matter in this problem for space or time efficiency because they both offer O(1) lookup time and use O(n) space. Array is possible because we are given the number of vertices n, and also improves the conciseness without needing to unwrap optionals + specify defaults.
2. Note that we can remove the visited array because a node without a color hasn't been visited. I have kept the visited array because it's an optimisation with no effect on overall time/space comp.
3. I've offered DFS and BFS variants depending on the problem. DFS has better space complexity for dense graphs, whereas BFS has better space complexity for sparse graphs. BFS also fails with the shortest path to a cycle (may or may not improve time comp depending on graph).

Summary

We can solve the Bipartite graph detection problem using modified graph traversal w/ cycle detection. Cycle detection is a useful technique for many graphs questions.