c# - 在加权图 C# 实现中查找最大权重团

Question

是否有在 C# 中的加权图中查找最大权重团的免费实现？

Answer 1

您可以阅读论文“A fast algorithm for the maximum clique problem”，您会发现本文提出的一种有效的最大团算法。此外，最大加权算法可以在“A new algorithm for the maximum weighted clique problem”中找到。这是伪代码:

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 标记了我们目前找到的最大 clique 大小，全局变量 found 标记了我们是否找到了更大的 clique。数组 c[] 记录了 Si 的最大团大小。 size 记录局部递归中的最大团大小。

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

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