爲圖表着色，以便每個節點都是彩色的或與彩色節點相鄰

Question

假設您有一個連通無向圖G.您希望G中的每個節點都是彩色的或與彩色節點相鄰。設計一個算法來適當地爲圖G着色。您只能對樓層（n/2）節點着色，其中n是節點的總數。

我嘗試了一個解決方案，但是我發現它沒有完全解決約束問題，我想要一個微調或被告知我在錯誤的軌道上。

我的解決方案基本上是運行BFS，並在每個「三級」着色節點。但是我發現了一個失敗的實例 - 只有三個節點的鏈表。如果我爲頭部或尾部着色，那麼其中一個節點距離彩色節點的距離爲2，並且我不太確定如何保證中間節點將被着色。

Answer 1

選擇一個根並生成一個帶有DFS的生成樹。

然後在每個第二級着色節點。根據選擇何種顏色選擇最少的節點，選擇偶數級別還是奇數級別。