请复习一下我的检测二分图的算法

Question

二分图是一个图，它的顶点可以分为两个独立的集合，U和V，使得每条边(U，V(要么连接一个从U到V的顶点，要么连接一一个从V到U的顶点。换句话说，对于每条边(U，V(，要么U属于U，要么V属于V，要么U属于V，V属于U。我们也可以说，没有边连接同一集合的顶点。

有关更多信息和bfs方法：https://www.geeksforgeeks.org/bipartite-graph/

=================================================

我知道有一种众所周知的BFS方法可以检测二分图，但我想知道下面的方法是否也有效。

Remove a random node (let's call it A) from graph.
Using recursion, divide other nodes into 2 independent sets.
Add back A to one of the sets. If that is not possible, return "Not Bipartite"
Base case: Empty graph is bipartite since it is divided into two empty sets. 

Answer 1

如果你有二分图

*---*---A---*---*

然后随机选择A，你得到

*---*       *---*

作为一个子问题，并且没有足够的信息来对匿名端点进行分组，从而保证A可以被添加回来。