# Part 21: Checking If An Undirected Graph Is Bipartite

### JB ・2 min read

CS Level Up Series (23 Part Series)

1) CS Level Up Series: Part 0
2) Part 1: Learning Dynamic Arrays
3 ... 21
3) Part 2: Learning Linked Lists
4) Part 3: Learning Stacks
5) Part 4: Learning Queues
6) Part 5: Learning Hash Tables
7) Part 6: Learning Binary Search Trees
8) Part 7: Learning Binary Heaps
9) Part 8: Learning Priority Queues
10) Part 9: Learning Graphs
11) Part 10: Learning Tries
12) Part 11: Learning Binary & Bit Manipulation
13) Part 12: Common Sorting Algorithms
14) Part 13: Searching Algorithms
15) Part 14: Permutations, Combinations, & Subsets
16) Part 15: NP-Complete & Fibonacci Heap
17) Part 16: Detecting Graph Cycles With Depth-First Search
18) Part 17: Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Part 18: Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Part 19: Finding Articulation Points & Bridges in Undirected Graphs
21) Part 20: Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Part 21: Checking If An Undirected Graph Is Bipartite
23) Part 22: Extending An Iterator

If you are unfamiliar with graphs, check out some of my earlier posts on them.

## Resources:

Takeaways:

- A bipartite graph (bigraph) is a graph where the vertices can be divided into two disjoint, independent, sets
`U`

and`V`

. Every edge will connect a vertex from one set to the other (without self referencing edges - I.E edges going from a vertex in`U`

to another vertex in`U`

). - One way to visualize a bipartite graph, is to colour all the vertices in a set the same colour. Set
`U`

could be red vertices, whereas`V`

could be black. This would mean an edge would always consist of a red and black pair of vertices. - This type of two-colouring is impossible in non-bipartite graphs. Think of a graph with three vertices arranged in a triangle. We cannot represent this graph as two independent sets, and we cannot two-colour it in such a way that will allow each edge to have different coloured endpoints.
- One way in which we can check if a graph is bipartite, is to run a depth-first search (DFS) over the vertices. Applying two colouring to the graph.
- Start at a random vertex
`V`

and colour it colour1 (red, for example). - Colour all adjacent vertices
`U`

the opposite colour of`V`

. For each adjacent`U`

, also recursively call our DFS routine. - If a graph is bipartite, we can complete this two-colouring without a contradiction.
- If the graph is not bipartite, then at some point a vertex will get both colours - and this contradiction means we cannot achieve a two-colouring of the graph.

- Start at a random vertex
- Time complexity is
`O(V + E)`

for an adjacency list. Space complexity is`O(V)`

. For an adjacency matrix, the time & space complexity would be`O(V^2)`

.

Undirected graph that can be two-coloured:

Undirected graph that cannot be two-coloured:

Below are implementations for checking if undirected graphs are bipartite. There is solutions for both undirected adjacency list & adjacency matrix representations of graphs:

As always, if you found any errors in this post please let me know!

CS Level Up Series (23 Part Series)

1) CS Level Up Series: Part 0
2) Part 1: Learning Dynamic Arrays
3 ... 21
3) Part 2: Learning Linked Lists
4) Part 3: Learning Stacks
5) Part 4: Learning Queues
6) Part 5: Learning Hash Tables
7) Part 6: Learning Binary Search Trees
8) Part 7: Learning Binary Heaps
9) Part 8: Learning Priority Queues
10) Part 9: Learning Graphs
11) Part 10: Learning Tries
12) Part 11: Learning Binary & Bit Manipulation
13) Part 12: Common Sorting Algorithms
14) Part 13: Searching Algorithms
15) Part 14: Permutations, Combinations, & Subsets
16) Part 15: NP-Complete & Fibonacci Heap
17) Part 16: Detecting Graph Cycles With Depth-First Search
18) Part 17: Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Part 18: Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Part 19: Finding Articulation Points & Bridges in Undirected Graphs
21) Part 20: Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Part 21: Checking If An Undirected Graph Is Bipartite
23) Part 22: Extending An Iterator

Classic DEV Post from Nov 23 '19