编写一个程序，判断一个图是否为二分图。
def is_bipartite(graph):color = {}# 用于记录每个节点的颜色
def dfs(node, c):
color = c
for neighbor in graph:
if neighbor not in color:
if not dfs(neighbor, 1 - c):
return False
elif color == c:
return False
return True
for node in graph:
if node not in color:
if not dfs(node, 0):
return False
return True
# 测试
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print(is_bipartite(graph))# 输出 True
graph = {
'A': ['B', 'C'],
'B': ['A', 'C'],
'C': ['A', 'B']
}
print(is_bipartite(graph))# 输出 False
页:
[1]