编写一个程序，判断一个图是否为二分图。

小九九

1. def is_bipartite(graph):
   
2.    color = {}  # 用于记录每个节点的颜色
   
3. 
   
4.    def dfs(node, c):
   
5.        color[node] = c
   
6. 
   
7.        for neighbor in graph[node]:
   
8.            if neighbor not in color:
   
9.                if not dfs(neighbor, 1 - c):
   
10.                    return False
    
11.            elif color[neighbor] == c:
    
12.                return False
    
13. 
    
14.        return True
    
15. 
    
16.    for node in graph:
    
17.        if node not in color:
    
18.            if not dfs(node, 0):
    
19.                return False
    
20.    
    
21.    return True
    
22. 
    
23. # 测试
    
24. graph = {
    
25.     'A': ['B', 'C'],
    
26.     'B': ['A', 'D'],
    
27.     'C': ['A', 'D'],
    
28.     'D': ['B', 'C']
    
29. }
    
30. print(is_bipartite(graph))  # 输出 True
    
31. 
    
32. graph = {
    
33.     'A': ['B', 'C'],
    
34.     'B': ['A', 'C'],
    
35.     'C': ['A', 'B']
    
36. }
    
37. print(is_bipartite(graph))  # 输出 False
    

复制代码