二分图同构判定：需设计跨编程语言的简易算法

二分图同构的核心是：两个二分图能通过顶点置换，让顶点划分和邻接关系完全匹配。结合邻接矩阵的思路，可实现一个跨语言的简易判定算法，步骤如下：

1. 前置校验 #

• 若输入未明确是二分图，先通过染色法验证（可选）；
• 将两个二分图拆分为左右顶点集：设图G的划分为(G₁, G₂)，图H的划分为(H₁, H₂)。若|G₁|≠|H₁|或|G₂|≠|H₂|，直接判定不同构。

2. 构建二分邻接矩阵 #

对每个二分图，生成一个行对应左部顶点、列对应右部顶点的矩阵：

• 矩阵元素M[i][j] = 1：左部第i个顶点与右部第j个顶点相连；
• 矩阵元素M[i][j] = 0：无连接关系。

3. 矩阵标准化（关键步骤） #

顶点编号是任意的，需通过置换行/列将矩阵转化为唯一的标准形式：

• 行排序：把每行转为二进制字符串（或整数），按字典序对行重新排列；
• 列排序：把每列转为二进制字符串（或整数），按字典序对列重新排列；
• 重复上述行、列排序操作2-3次（直到矩阵不再变化），得到该图的标准二分邻接矩阵。

4. 同构判定 #

将两个二分图的标准矩阵逐元素对比：

• 若完全一致，则判定同构；
• 若存在差异，则判定不同构。

优化技巧 #

• 先计算不变量快速排除：比如分别统计左右部顶点的度数序列，排序后若不匹配，直接判定不同构；
• 优先处理顶点数更少的顶点集置换，减少排序计算量。

内容的提问来源于stack exchange，提问作者Gleb Khineev