小白学算法-数据结构和算法教程: 队列的应用

用户1418987

发布于 2023-10-26 14:17:52

1410

发布于 2023-10-26 14:17:52

文章被收录于专栏：coder

检查给定图是否是二分图

二分图是一种图，其顶点可以分为两个独立的集合 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")

输出