二部图深度优先广度优先

### 二部图中深度优先搜索和广度优先搜索

#### 深度优先搜索(DFS)

在处理二部图时，深度优先搜索可以用于检测图形是否为有效的二部图。通过给定一个起始节点并标记其颜色，随后递归地尝试对其未访问的邻居节点着相反的颜色。如果在整个过程中没有遇到冲突，则该图为二部图。

def is_bipartite_dfs(graph, start_node=0):
    colors = {}
    
    def dfs(node, color):
        if node in colors:
            return colors[node] == color
        
        colors[node] = color
        for neighbor in graph[node]:
            if not dfs(neighbor, 1 - color):  
                return False
                
        return True
    
    return all(dfs(component, 0) for component in range(len(graph)) if component not in colors)

此函数`is_bipartite_dfs()`接收一个邻接表形式表示的无向图作为输入参数，并返回布尔值指示图是否为二分图[^2]。

#### 广度优先搜索(BFS)

对于同样的目的——验证二部性质，也可以采用广度优先的方法来进行染色测试：

from collections import deque

def is_bipartite_bfs(graph, start_node=0):
    queue = deque([start_node])
    visited = set()
    colored_nodes = {start_node : 0}
    
    while queue:
        current_node = queue.popleft()

        if current_node in visited:
            continue
            
        visited.add(current_node)
        
        for adjacent_node in graph[current_node]:
            if adjacent_node in colored_nodes and colored_nodes[adjacent_node] == colored_nodes[current_node]:
                return False
                
            elif adjacent_node not in colored_nodes:
                colored_nodes[adjacent_node] = 1 - colored_nodes[current_node]
                queue.append(adjacent_node)
                
    return True

上述代码片段展示了如何使用队列结构执行层次遍历来检查是否存在违反二部分割的情况；一旦发现两个相连结点具有相同颜色即刻终止程序并报告失败[^4]。