无向图G=(V,E)的二分图判断

二分图的概念

无向图$G=(V,E)$的顶点集$V$可分为两个集合$V_1$，$V_2$，$s.t.\forall (u,v)\in E,\exists u\in V_1,v\in V_2$ 或$u\in V_2,v\in V_1$，则称图$G$为二分图，即所有的边都位于$V_1$和$V_2$之间。

判断方法

判断二分图的常用方法为染色法。通过遍历整个无向图$G$，对图中的顶点进行有规律的染色。

染色步骤为：选择一个起始顶点$u$，将其染成黑色$BLACK$；然后遍历所有与$u$相邻的顶点$v$，将$v$染成白色$WHITE$；同时再将与顶点$v$相邻的顶点$w$，将$w$染成黑色$BLACK$；依次进行下去，直到遍历结束。

若图中还有顶点未遍历，则重复上述染色步骤。

如果我们能够完成染色步骤，那么该无向图为二分图。

如果染色过程中产生了冲突，即当遍历到某个顶点$x$时，该顶点已经染色，并且$x$的颜色与我们准备给其染成的颜色不一致，则表示该无向图不是二分图。

判断二分图的过程

可以使用深度优先搜索或广度优先搜索对无向图进行遍历。

考虑到无向图可能是一个非连通图，因此需要多次执行广度优先搜索或深度优先搜索才能完全遍历所有的顶点。

BFS Pseudocode

$G=(V,E)$

$\forall$ 顶点$u\in V$，定义$visited[u]$存储搜索过程中顶点$u$的染色情况：

$UNVISITED$：未访问状态。
$WHITE$：标记为白色。
$BLACK$：标记为黑色。

定义First-in, first-out (FIFO)队列$Q$，存放搜索中的顶点。

BFS-Pseudocode(G)
	// 初始化顶点的颜色
	for every u in V[G]
		visited[u] = UNVISITED

	//初始化队列
	Q = nil

	// 遍历无向图的全部顶点，进行染色
	for every u in V[G]
		if visited[u] == UNVISITED then
			result = BFS(u)
			do if result == false then
				return false
	return true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

BFS(u)
	// 开始搜索时设置源顶点u的颜色为BLACK，并放入队列中
	Q.push(u)
	visited[u] = BLACK
	// Q队列存放搜索中的顶点；该顶点已被染色，但其邻接表的顶点还尚未被染色
	while Q  is not empty
		do u = Q.pop()
		for v in Adj[u] // 顶点u的邻接表
			do if  visited[v] == UNVISITED then // 对未访问的顶点染成与u相反的颜色
				visited[v] = visited[u] == WHITE ? BLACK: WHITE
				Q.push(v)
			else if visited[u] == visited[v] then // 染色过程中产生了冲突
				return false // 不是二分图
			else then
				trivial
	return true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

DFS Pseudocode

DFS-Pseudocode(G)
	// 初始化顶点的颜色
	for every u in V[G]
		visited[u] = UNVISITED

	// 判断结果
	result = true

	// 遍历无向图的全部顶点，进行染色
	for every u in V[G]
		if visited[u] == UNVISITED then
			DFS(u, BLACK)
			do if result == false then
				return false
	return true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

DFS(u, color)
	// 顶点u的染色为color
	visited[u] = color
	for v in Adj[u] // 顶点u的邻接表
		do if  visited[v] == UNVISITED then
			// 对未访问的顶点染成与u相反的颜色
			reverseColor = color == WHITE ? BLACK: WHITE
			DFS(v, reverseColor)
			do if result == flase then // 深度遍历过程中，提前判断，提前结束
				return
		else if color == visited[v] then // 染色过程中产生了冲突
			result = false // 不是二分图
			return
		else then
			trivial
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15