確定是否可以使用兩種顏色對無向圖進行着色

Question

有關如何確定無向圖只能使用兩種顏色進行着色的任何提示？ 這怎麼可以在java中實現？

Answer 1

在圖表上做一個breadth-first search。在每個深度上，將節點着色爲一種顏色，例如紅色，並且在奇數深度處，將節點着色爲藍色。每當你有一個非樹邊緣（你已經訪問過的兩個節點之間的一條邊）時，驗證顏色是不同的。如果圖形包含多個連接的組件，則只需在每個組件上重複搜索即可。

Answer 2

這與確定圖形是否是二分相同。爲此，您必須檢查圖中是否存在奇數長度的循環。爲此，您需要在圖表上進行廣度優先搜索。如果在BFS中的任何級別上，在同一級別的節點之間存在任何邊緣，則圖形不是雙方的，即，它不能僅使用兩種顏色着色。 （假設約束條件是相鄰節點應該是不同的顏色）