跳至主要內容

 

labuladong约 604 字大约 2 分钟数据结构图论算法

Info

算法可视化编辑器上线,点击体验open in new window

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
785. Is Graph Bipartite?open in new window785. 判断二分图open in new window🟠
886. Possible Bipartitionopen in new window886. 可能的二分法open in new window🟠
-剑指 Offer II 106. 二分图open in new window🟠

Tip

本文有视频版:二分图判定算法及应用open in new window。建议关注我的 B 站账号,我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

我之前写了好几篇图论相关的文章:

图遍历算法

名流问题

并查集算法计算连通分量

环检测和拓扑排序

Dijkstra 最短路径算法

今天继续来讲一个经典图论算法:二分图判定。

二分图简介

在讲二分图的判定算法之前,我们先来看下百度百科对「二分图」的定义:

二分图的顶点集可分割为两个互不相交的子集,图中每条边依附的两个顶点都分属于这两个子集,且两个子集内的顶点不相邻。

其实图论里面很多术语的定义都比较拗口,不容易理解。我们甭看这个死板的定义了,来玩个游戏吧:

给你一幅「图」,请你用两种颜色将图中的所有顶点着色,且使得任意一条边的两个端点的颜色都不相同,你能做到吗

这就是图的「双色问题」,其实这个问题就等同于二分图的判定问题,如果你能够成功地将图染色,那么这幅图就是一幅二分图,反之则不是:

在具体讲解二分图判定算法之前,我们先来说说计算机大佬们闲着无聊解决双色问题的目的是什么。

加载中...