二分图判定算法
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 785. Is Graph Bipartite? | 🟠 |
| 886. Possible Bipartition | 🟠 |
Prerequisites
Before reading this article, you should first learn:
Tip
本文有视频版：Bipartite Graph Determination Algorithm and Applications。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
Today, we will discuss a classic graph theory algorithm: Bipartite Graph Determination.
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 a vertex from one subset to a vertex from the other subset, and no two vertices within the same subset are adjacent.
Many definitions in graph theory can be quite convoluted and hard 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 such that the endpoints of each edge have different colors?
This is known as the "Two-Color Problem," which is equivalent to the bipartite graph determination problem. If you can successfully color the graph, then it is a bipartite graph; otherwise, it is not:
Before diving into the algorithm for determining bipartite graphs, let's first discuss why computer scientists were interested in solving the Two-Color Problem.