給定無向圖G=(V, E), U⊆V, 若對任意u, v∈U, 有(u,v) ∈ E, 則稱U是G的一個完全子圖.
G的完全子圖U是G的一個團當且僅當U不包含在G的更大的完全子圖中,G的最大團是指G中所含頂點數最多的團.
無向圖G的最大團和最大獨立集問題都可以用回溯法在O(n2^n)時間内解決.圖G的最大團和最大獨立集問題都可以看做圖G的頂點集V的子集選取問題.是以,我們可以用子集樹表示問題的解空間.
解最大團問題的回溯法和解裝載問題的回溯法十分相似.設目前擴充結點Z位于解空間樹的第i層.在進入左子樹前,必須确認還有足夠多的可選擇頂點,使得算法有可能在右子樹中找到更大的集.
具體代碼如下:
運作結果如下:
由此建構出的的子集樹為:
應該比較清晰,大家可以試着自己畫一畫.
參考畢方明老師《算法設計與分析》課件.
歡迎大家通路個人部落格網站---喬治的程式設計小屋,一起加油吧!