在加权图中找到最大权重集团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行

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