How to Determine a Bipartite Graph
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 785. Is Graph Bipartite? | 🟠 |
| 886. Possible Bipartition | 🟠 |
Prerequisite Knowledge
Before reading this article, you need to learn:
Today, we will discuss a classic graph theory algorithm: Bipartite Graph Detection.
Introduction to Bipartite Graphs
Let's start with the definition of a bipartite graph:
The vertex set of a bipartite graph can be divided into two disjoint subsets, where each edge connects vertices from the two different subsets, and vertices within the same subset are not adjacent.
In fact, many definitions in graph theory can be quite complex and difficult to understand. Instead of focusing on this rigid definition, let's play a game:
Given a "graph", can you color all the vertices using two colors so that the endpoints of every edge have different colors?
This is known as the "two-color problem" of graphs, which is equivalent to the problem of detecting bipartite graphs. If you can successfully color the graph, it is a bipartite graph; otherwise, it is not:
Before we delve into the algorithm for detecting bipartite graphs, let's discuss why computer scientists were interested in solving the two-color problem in the first place.