图--判断二分图
文章目录
把相邻顶点染成不同颜色的问题叫做图着色问题。对图进行染色所需要的最小颜色数目叫做最小作色数字。最小作色数为2的叫做二分图。
class Solution(object):
def isBipartite(self, graph):
"""
:type graph: List[List[int]]
:rtype: bool
"""
def dfs(v,c):
color[v] = c
for i in range(0,len(graph[v])):
# 如果相邻的顶点同色,则返回False
if color[graph[v][i]]==c:return False
# 如果相邻的顶点还没被染色 染成-c
if color[graph[v][i]]==0 and not dfs(graph[v][i],-c):return False
# 如果所有的顶点都染色了 返回True
return True
color = [0 for _ in range(len(graph))]
for i in range(len(graph)):
if color[i]==0:
if not dfs(i,1):
return False
return True
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论