在加權圖中找到最大權重集團C＃實現

Question

在C＃中有權利圖中找到最大權重集羣的免費可用實現嗎？

Answer 1

找到最大集團是一個NP難題。你可以在Clique problem（維基百科）找到有用的東西。

Answer 2

您可以閱讀論文「最大集團問題的快速算法」，您將找到本文提出的有效最大集團算法。另外，最大加權算法可以在「用於最大加權集團問題的新算法」中找到。這裏是僞代碼：

1 **FUNCTION CLIQUE(U, size)** 
2 if |U| = 0 then 
3  if size > max then 
4   max ← size 
5   New record; save it. 
6   found ← true 
7  end 
8  return 
9 end 
10 while |U| != ∅ do 
11  if size + weight(|U|) <= max then 
12   return 
13  end 
14  i ← min{ j|vj ∈ U} 
15  if size + c[i] <= max then 
16   return 
17  end 
18  U ← U ∖ {vi} 
19  CLIQUE(U ∩ N(vi); size + weight(vi)) 
20  if found = true then 
21   return 
22  end 
23 end 
24 return 
25 **FUNCTION NEW()** 
26 max ← 0 
27 for i ← n downto 1 do 
28  found ← false 
29  CLIQUE(Si ∩ N(vi), weight(i)) 
30  c[i] ← max 
31 end 
32 return 

我們假設Si代表有比我大的指數，例如頂點{V1，V1 + 1，...，VN}。 N（vi）表示vi的相鄰頂點。全局變量最大表示我們現在發現的集團的最大尺寸，而全局變量找到表示我們是否找到了更大的集團。數組c []記錄Si的最大集團大小。 大小在本地遞歸記錄最大團大小。

有幾種修剪策略，它能避免無用的搜索，特別是在第11行和15行

您可以使用哈希表來實現這個算法。