Class BipartiteUtil

java.lang.Object
cloud.opencode.base.graph.algorithm.BipartiteUtil
public final class BipartiteUtil extends Object
Bipartite Graph Detection Utility 二部图检测工具类

Determines whether a graph is bipartite using BFS 2-coloring, and computes the vertex partition or provides an odd-cycle witness.

使用BFS双着色判断图是否为二部图，并计算顶点分区或提供奇数环证据。

Features | 主要功能:

  • Check if a graph is bipartite - 检查图是否为二部图
  • Compute left/right vertex partition - 计算左/右顶点分区
  • Return odd cycle witness when not bipartite - 非二部图时返回奇数环证据
  • Handle disconnected components - 处理非连通分量
  • Directed graphs treated as undirected - 有向图按无向图处理

Usage Examples | 使用示例:

Graph<String> graph = OpenGraph.undirected();
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "D");
graph.addEdge("D", "A");

boolean bipartite = BipartiteUtil.isBipartite(graph);  // true (even cycle)

BipartiteUtil.BipartiteResult<String> result = BipartiteUtil.partition(graph);
Set<String> left = result.left();   // e.g., {"A", "C"}
Set<String> right = result.right(); // e.g., {"B", "D"}

Performance | 性能特性:

  • Time complexity: O(V + E) - 时间复杂度: O(V + E)
  • Space complexity: O(V) - 空间复杂度: O(V)
Since:
JDK 25, opencode-base-graph V1.0.3
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • isBipartite

      public static <V> boolean isBipartite(Graph<V> graph)
      Check if the graph is bipartite. 检查图是否为二部图。

      For directed graphs, edges are treated as undirected.

      对于有向图，边按无向处理。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph to check | 要检查的图
      Returns:
      true if the graph is bipartite | 如果图是二部图返回true

    • partition

      public static <V> BipartiteUtil.BipartiteResult<V> partition(Graph<V> graph)
      Compute the bipartite partition or find an odd cycle witness. 计算二部图分区或查找奇数环证据。

      For directed graphs, edges are treated as undirected. Handles disconnected components by iterating over all unvisited vertices.

      对于有向图，边按无向处理。通过遍历所有未访问顶点来处理非连通分量。

      Type Parameters:
      V - the vertex type | 顶点类型
      Parameters:
      graph - the graph to partition | 要分区的图
      Returns:
      bipartite result with partition or odd cycle | 包含分区或奇数环的二部图结果