P89 - 判断二分图

Determine whether a graph is bipartite
官方模块：Problems.P89　核心函数：bipartite

核心思想

二分图等价于可以用两种颜色给顶点着色，使每条边两端颜色不同。对每个连通分量做 BFS；访问边 (u,v) 时，未着色的 v 获得 u 的相反颜色，已着色则检查冲突。

实现

方法一：标准实现

 1bipartite :: G -> Bool
 2bipartite graph = colorComponents allVertices Map.empty
 3  where
 4    allVertices = fst (canonical graph)
 5
 6    colorComponents remaining colors
 7      | Set.null remaining = True
 8      | otherwise = case bfs [start] (Map.insert start False colors) of
 9          Nothing      -> False
10          Just colors' -> colorComponents
11            (Set.difference remaining (Map.keysSet colors')) colors'
12      where start = Set.findMin remaining
13
14    bfs [] colors = Just colors
15    bfs (u:queue) colors = process (Set.toList (neighbors u graph)) queue colors
16      where
17        expected = not (colors Map.! u)
18        process [] rest current = bfs rest current
19        process (v:vs) rest current = case Map.lookup v current of
20          Just color | color /= expected -> Nothing
21                     | otherwise -> process vs rest current
22          Nothing -> process vs (rest ++ [v]) (Map.insert v expected current)

方法二：DFS 二着色

 1bipartiteDFS :: G -> Bool
 2bipartiteDFS graph = colorAll (Set.toList vertices) Map.empty
 3  where
 4    vertices = fst (canonical graph)
 5
 6    colorAll [] _ = True
 7    colorAll (vertex:rest) colors = case Map.lookup vertex colors of
 8      Just _  -> colorAll rest colors
 9      Nothing -> case paint vertex False colors of
10        Nothing      -> False
11        Just colors' -> colorAll rest colors'
12
13    paint vertex color colors = case Map.lookup vertex colors of
14      Just existing
15        | existing == color -> Just colors
16        | otherwise         -> Nothing
17      Nothing -> foldNeighbors
18        (Set.toList (neighbors vertex graph))
19        (Map.insert vertex color colors)
20      where
21        foldNeighbors [] current = Just current
22        foldNeighbors (neighbor:rest) current = do
23          colored <- paint neighbor (not color) current
24          foldNeighbors rest colored

DFS 版本把期望颜色作为递归参数传入。遇到已着色顶点时立即比较颜色；未着色时先记录，再递归地给所有邻居涂相反颜色。

方法对比

方法	遍历策略
BFS	队列逐层传播颜色
DFS	递归沿路径传播颜色

测试

1>>> bipartite (toG (Paths [[1,2,3,4],[1,4,5,2]]))
2True
3>>> bipartite (toG (Paths [[1,2,3,4],[1,4,5,2],[1,3]]))
4False
5>>> bipartiteDFS (toG (Paths [[1,2,3,4],[1,4,5,2]]))
6True

这里用列表尾部追加模拟队列，严谨的 $O(V+E)$ 实现可换用 Data.Sequence。

参考

← P88 连通分量 | P90 N 皇后 →