检查给定图是否是二分图
二分图是一种图，其顶点可以分为两个独立的集合 U 和 V，使得每条边 (u, v) 要么连接从 U 到 V 的顶点，要么连接从 V 到 U 的顶点。换句话说，对于每个边 (u, v)，要么 u 属于 U，v 属于 V，要么 u 属于 V，v 属于 U。我们也可以说，不存在连接同一集合的顶点的边。
如果图着色可以使用两种颜色使得集合中的顶点使用相同颜色着色，则二分图是可能的。
请注意，可以使用两种颜色对具有偶数循环的循环图进行着色。例如，请参见下图。
不可能使用两种颜色对具有奇数循环的循环图进行着色。
检查图是否为二分图的算法：
解法步骤：
一种方法是使用 回溯算法 m 着色问题来检查图是否为 2-colorable 。
以下是一个使用广度优先搜索 (BFS) 来确定给定图是否为二分图的简单算法。
- 将红色分配给源顶点（放入 U 组）。
- 将所有邻居涂成蓝色（放入集合 V 中）。
- 将所有邻居的邻居涂成红色（放入集合 U 中）。
- 为所有顶点分配颜色，使其满足 m 路着色问题的所有约束，其中 m = 2。
- 在分配颜色时，如果我们找到与当前顶点颜色相同的邻居，则图不能用 2 个顶点着色（或者图不是二分图）
回溯算法
Python:
# Python 程序查找 给定图形是否为二方图
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)] \
for row in range(V)]
# 如果图 G[V][V] 返回 true，则此函数返回 true。
# 是二方图，否则返回 false
def isBipartite(self, src):
colorArr = [-1] * self.V
# 将第一种颜色指定给源
colorArr[src] = 1
# 创建一个顶点编号的队列（先进先出），
# 将源顶点入队以进行BFS遍历。
queue = []
queue.append(src)
# 在队列中有顶点时运行 （类似于 BFS）
while queue:
u = queue.pop()
# 如果存在自循环，则返回 false
if self.graph[u][u] == 1:
return False;
for v in range(self.V):
# An edge from u to v exists and destination
# v is not colored
if self.graph[u][v] == 1 and colorArr[v] == -1:
# Assign alternate color to this
# adjacent v of u
colorArr[v] = 1 - colorArr[u]
queue.append(v)
# An edge from u to v exists and destination
# v is colored with same color as u
elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]:
return False
# If we reach here, then all adjacent
# vertices can be colored with alternate
# color
return True
# Driver program to test above function
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
print ("Yes" if g.isBipartite(0) else "No")输出
是的复杂度分析
时间复杂度：O(V*V) 作为邻接矩阵用于图，但可以通过使用邻接列表将其变为 O(V+E)
辅助空间：由于队列和颜色向量，O(V)。
上述算法仅在 图是连通的情况下才有效。在上面的代码中，我们总是从源 0 开始，并假设从源 0 访问顶点。一个重要的观察是，没有边的图也是二分图。请注意，二分条件表示所有边都应从一组到另一组。
我们可以扩展上面的代码来处理图未连接的情况。对于所有尚未访问的顶点，重复调用上述方法。
Python：
# Python3 程序来找出 给定图形是否为二方图
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)]
for row in range(V)]
self.colorArr = [-1 for i in range(self.V)]
# 如果图 G[V][V] 返回 true，则此函数返回 true。 是二方图，否则返回 false
def isBipartiteUtil(self, src):
# 创建顶点编号队列（先进先出）并
# 为 BFS 遍历登记源顶点
queue = []
queue.append(src)
# 在队列中有顶点时运行 (类似于 BFS）
while queue:
u = queue.pop()
# 如果存在自循环，则返回 false
if self.graph[u][u] == 1:
return False
for v in range(self.V):
# 存在一条从 u 到 v 的边，并且目的地 v 没有着色
if (self.graph[u][v] == 1 and
self.colorArr[v] == -1):
# 为 u 的相邻 v
self.colorArr[v] = 1 - self.colorArr[u]
queue.append(v)
# 存在一条从 u 到 v 的边，且目的地 v 的颜色与 u 相同
elif (self.graph[u][v] == 1 and
self.colorArr[v] == self.colorArr[u]):
return False
return True
def isBipartite(self):
self.colorArr = [-1 for i in range(self.V)]
for i in range(self.V):
if self.colorArr[i] == -1:
if not self.isBipartiteUtil(i):
return False
return True
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]
print ("Yes" if g.isBipartite() else "No")输出
是的复杂度分析
时间复杂度：O(V+E)。
辅助空间：O(V)，因为我们有一个 V 大小的数组。
如果使用邻接表来表示图，时间复杂度将为 O(V+E)。
适用于连接图和断开图。