測試二分圖（testing bipartiteness）

若能把一張圖的頂點分成兩個陣營，使每條邊都跨在兩陣營之間、絕不落在同一陣營內，這張圖就是二分圖——像把賓客安排到兩桌使任兩個朋友不同桌，或一份每個任務都把工人連到工作的排程。最自然的想像方式是著色：把每個頂點塗成紅或藍，使任一條邊都不連接同色的兩個頂點。許多真實情境（匹配、衝突圖、排程）正是「這能不能分成兩側？」的問題，而圖搜尋一趟就能回答。

這個測試是一趟著色走訪。從每個未拜訪的頂點跑 BFS（或 DFS）；把起點塗紅，並把每個新發現的頂點塗成與你由之抵達它的那個頂點相反的顏色。若你曾發現某條邊的兩端已帶有相同顏色，就停下：這張圖不是二分圖。若你走完都沒有這種衝突，它就是。為何正確？在 BFS 中，一條同色邊必定連接兩個層級奇偶相同的頂點，把兩端在 BFS 樹中往上追到它們的共同祖先，會產生一個長度為奇數的環。所以著色失敗不是你選色的偶然——它是一個真正的奇環，而經典定理說：一張圖是二分圖，恰當它沒有奇環。正是這個定理把「我無法把它二著色」升級為確鑿的「它不可能被二著色」。

這跑在 O(n + m)，即一趟走訪的成本，它既判定了問題，又在成功時免費奉上實際的兩側分割。它是二分圖匹配與許多排程模型的入口。要分清的一個提醒：二分圖意味沒有奇環，而偶環完全沒問題——4 環或 6 環都是二分圖。另外，你必須測試每一個連通分量（從每個未著色的頂點開始搜尋），因為一張圖可能在一塊裡是二分的、卻在另一塊裡有衝突。