## 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 {
}

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
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()
if !visited[neighbour] {
visited[neighbour] = true
color[neighbour] = 1 - color[curr]
queue.append(neighbour)
} else if color[neighbour] == color[curr] {
return false
}
}
}
return true
}
``````