Java实现无向图二分图判断代码超时问题排查

直接导致超时的死循环问题 #

你代码中遍历当前节点邻居的内层循环没有对循环变量做自增操作：

int i = 0;
while (i<list.size()){
    GraphNode node = list.get(i);
    // 所有逻辑中都没有i++语句
}

i永远等于0，会重复读取第一个邻居节点陷入死循环，这是触发超时报错的直接原因。

其他核心逻辑错误 #

• 未处理多连通分量场景：输入为整个图的全量节点列表，无向图可能存在多个互不连通的独立分量，你仅从graph.get(0)启动遍历，剩余连通分量完全没有校验，会导致结果错误。
• 二分性校验规则错误：二分图的核心要求是相邻节点必须属于不同分组，你仅校验邻居是否属于上一轮扩展节点的逻辑无法识别奇数长度环。比如三角形环1-2-3-1，遍历顺序为1→2→3时，3的邻居1不属于上一轮（2所在层）的集合，你的逻辑不会报错，但该图实际不是二分图。
• iterate集合未清空：你每轮处理完节点后没有清空iterate集合，下一轮的新节点会不断追加到旧集合中，导致compare集合完全不符合「存储上一轮扩展节点」的设计预期，校验逻辑完全失效。
• 已访问节点标记时机不合理：你在处理完当前节点的所有邻居后才将其加入store集合，若多个节点的邻居指向同一个未处理节点，会出现重复入队的问题，增加不必要的性能开销。

修正思路 #

1. 修复内层循环的自增逻辑，或直接改用for-each遍历邻居列表避免手写循环变量出错。
2. 新增HashMap<GraphNode, Integer>存储每个节点的分组标记（0/1代表两个分组），初始状态所有节点无标记。
3. 遍历输入的全量节点列表，遇到无标记的节点就启动BFS，确保所有连通分量都被校验。
4. BFS过程中，若当前节点分组为color，则所有邻居节点如果未标记就赋值为1-color并入队，如果已标记则判断是否等于1-color，不符合则直接返回false。

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