只需要一個偽代碼,而不是整個運行代碼。對 DFS 演算法進行必要的修改,以便它可以檢查圖中的頂點是否可以用 0 和 1 進行標記,從而在具有相同標簽的頂點之間不存在邊。
uj5u.com熱心網友回復:
您正在尋找的圖稱為二分圖。對 DFS 的修改是這樣的(讓 color[node] 在所有節點的開頭都為 -1):
- 讓顏色[1] = 1。
- 從節點 1 啟動 DFS
- 在您的 DFS 中,為當前節點的所有未著色鄰居著色,其顏色與當前節點的顏色相反。
- 如果存在顏色等于當前節點顏色的彩色鄰居,則沒有解決方案。
轉載請註明出處,本文鏈接:https://www.uj5u.com/qukuanlian/434652.html
上一篇:對稱一維陣列Python
