在加权图C#实现中寻找最大权重团

你可以阅读《最大集团问题的快速算法》一文，你会发现本文提出的一种有效的最大集团算法。此外，在"最大加权集团问题的一种新算法"中还可以找到一种最大加权算法。这是伪代码：

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表示索引比i大的顶点，例如{vi，vi+1，…，vn}。N（vi）表示vi的相邻顶点。全局变量max标记我们目前发现的团的最大大小，发现的全局变量<em标记我们是否发现了更大的团。数组c[]记录Si的最大团大小。>size记录局部递归中的最大团尺寸

有几种修剪策略可以避免无用的搜索，尤其是在第11行和第15行。

您可以使用哈希表来实现此算法。

求最大团是一个NP难题。你可以在"派系问题"（维基百科）中找到一些有用的东西。