✕ 文件回写 ✕ 属性回写 ✓ 直接返回 ✓ 流式返回 ✓ 统计值

概述

二分图（Bipartite Graph）算法用于确定给定的图是否为二分图。通过应用该算法，可以在不同情况下识别和利用二分图的固有结构，实现有效的资源分配、任务分配和分组优化。

基本概念

二分图

二分图中的节点可以划分至两个不相交的集合，且图中的每条边都连接一个集合中的节点和另一个集合中的节点。换句话说，不存在连接同一集合内节点的边。

这是一个示例的二分图，它的节点可以划分至集合 V₁ = {A, D, E} 和 V₂ = {B, C, F}。

着色法

要确定一个图是否为二分图，一种常见的方法是进行图遍历并将每个访问的节点分配到两个不同的集合中。这个过程通常被称为对节点进行"着色"。在遍历过程中，如果遇到连接两个同一集合中的节点的边，则该图不是二分图。相反，如果所有的边连接来自不同集合的节点，那么该图是二分图。

在这个例子中，图 A 和图 B 都是二分图。图 C 不是二分图，因为它包含一个奇数环。奇数环（Odd Cycle）是指节点数为奇数的环路。二分图不能包含奇数环，因为无法使用两种颜色对奇数环中的所有节点进行着色，同时满足二分图的要求。这种特性，即二分图不包含任何奇数环，是二分图的基本特征之一。

特殊说明

• 自环边的两个端点是同一个节点，因此含有自环边的图都不是二分图。
• 二分图算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(bipartite)
• 本算法无参数

示例

示例图如下：

直接返回

algo(bipartite).params() as result 
return result

结果：result

流式返回

algo(bipartite).params().stream() as result 
return result

结果：result

统计返回

algo(bipartite).params().stats() as result 
return result

结果：result