判定给定图是否为二分图

题目描述请参考 LeetCode - 785

分析

二分图的充要条件是:任何一个结点回路的长度为偶数。

所以我们如果将定义实现就是一个正确的方法了。但是有个问题,这样需要穷举判定全部的回路,时间复杂度过高。
简单办法(参考引申):任选一个结点开始进行黑白交叉染色,起点开始奇数距离路径的结点全部都跟自己异色,偶数则同色。否则必然不是二分图,这一点也与定义一致,考虑到全部偶数距离的路径也包括回路,所以必是同色。因此当我们染色发生矛盾时就能知道这张图就不是二分图了。

*引申:任选一个结点a放入A集合,若给定图是二分图,则所有到a路径长度为偶数的结点均可放入A集合,否则均可放入A’集合,A与A’构成二分图。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
size = len(graph)
if not graph:
return False

edge, que, color, has = [[0 for _ in range(size)] for _ in range(size)], [], [0] * size, []

for x, i in enumerate(graph):
for y in i:
edge[x][y] = edge[y][x] = 1

for i in range(0, size):

if color[i] == 0:
que.append(i)
color[i] = 1

while que:
curr = que.pop()
has.append(curr)

for i in range(0, size):
if edge[curr][i]:
if color[i] == 0:
color[i] = -color[curr]
elif color[i] == color[curr]:
return False
if i not in has:
que.append(i)
return True