我的算法课中的一项任务是设计一个详尽的搜索算法来解决集团问题。也就是说，给定大小为n的图，算法应该确定是否存在大小为k的完整子图。我想我已经得到了答案，但我不禁认为它可以改进。这是我所拥有的：

版本 1

输入：由数组 A[0,... n -1] 表示的图，要查找的子图的大小k。

输出：如果存在子图则为真，否则为假

算法（在类似 python 的伪代码中）：

版本 2

输入：大小为 n x n 的邻接矩阵，k 是要查找的子图的大小

输出：大小为 k 的 A 中的所有完整子图。

算法（这次是函数式/Python 伪代码）：

有没有人有任何想法、意见或建议？这包括我可能错过的错误以及使其更具可读性的方法（我不习惯使用太多伪代码）。

版本 3

幸运的是，我在提交作业之前和我的教授谈过了。当我给他看我写的伪代码时，他笑着告诉我我做的工作太多了。其一，我不必提交伪代码；我只需要证明我理解这个问题。第二，他想要蛮力解决方案。所以我上交的东西看起来像这样：

输入：一个图 G = (V,E)，找到k的 clique 的大小

输出：如果集团确实存在则为真，否则为假

算法：

1. 求笛卡尔积 V ^k。
2. 对于结果中的每个元组，测试每个顶点是否相互连接。如果全部连接，则返回 true 并退出。
3. 返回 false 并退出。

更新：添加了第二个版本。我认为这正在变得更好，尽管我没有添加任何花哨的动态编程（我知道）。

更新 2：添加了更多评论和文档以使第 2 版更具可读性。这可能是我今天上交的版本。感谢大家的帮助！我希望我能接受多个答案，但我接受了对我帮助最大的人的答案。我会让你们知道我的教授的想法。

图是图的子图，其中任何顶点与其余顶点相连。

在 k- 问题中，输入是一个无向图和一个数字 k，如果存在，则输出是一个大小为 k 的 clof（或者，有时，所有大小为 k 的 cl）

“证明确定给定输入 G 和 k 是 NP 完全的G 拥有这两个子集。”

我们在我的算法课程中遇到了这个问题，一大群学生无法弄清楚。这是我们到目前为止所拥有的...

我们知道集团和独立集问题本身都是 NP-Complete 的。我们也知道这个问题的验证，给定一些“证书”在 NP 中。

问题是以某种方式将上述问题（包含独立集和派系）简化为完全由派系或独立集组成的问题（至少这是我们认为需要做的）。我们不知道如何在不丢失将还原还原到其原始形式所需的信息的情况下执行此还原。

有谁知道解决集团覆盖问题的库或一些代码（最好是Java）？

我找到了一个 OCaml版本，但我想使用一些我可以更容易集成的东西。

我还找到了 Java代码和 C 代码来查找图中的最大团，但我不知道如何利用此代码找到团覆盖（例如，迭代删除最大团，直到没有节点留下不会产生最佳解决方案）。

我目前正在开发一个应用程序，以在我的最后一年项目的图表中找到最大集团。我已经完成了大部分项目，并且刚刚开始测试应用程序。

该应用程序当前使用邻接列表作为输入，我想知道是否有人知道邻接列表随机生成器，以便我可以测试我的应用程序？

非常感谢

我试图解决一个基本的集团问题，但我坚持以下几点：

• what is is the minimum size of the largest clique in any graph with N nodes and M edges

• To Find the largest clique in a graph

请告诉我以上两种说法的区别。

对于一个大学项目，我正在尝试实现Bron–Kerbosch 算法，即在给定图中列出所有最大派系。

我正在尝试实现第一个算法（没有旋转），但我的代码在维基百科的示例中测试后并没有产生所有答案，到目前为止我的代码是：

为什么我只得到部分答案有什么帮助？

我在实现 Bron-Kerbosch 算法的 C 版本时遇到了一些问题：

1-我完全不了解算法的工作原理。我试图在互联网上找到参考资料，但所有这些参考资料都很糟糕，因为可怕的算法示例实现很糟糕，并且没有任何解释出现在伪代码上的一些任意命名的函数（例如 P(N) ）

2- 我在互联网上找到了一些 C++ 实现，但作者未能放入代码中使用的类，所以我留下了非常命名的变量，我什至不知道它们是什么类型（例如 compsub、nod、minnod , fixp, newne, newce)。

我能够翻译的一个代码是 SegFaulting。你能帮我理解算法/告诉我我的代码做错了什么吗？

一些有用的信息：

graph->matrix 是连接矩阵。

List_clear 返回列表的大小。

这是我的问题的上下文：

我有一个家庭作业问题：描述顶点大小的线性时间算法（即 O(|V|)），以确定图中是否存在所有顶点的最大度数为 3 的最大团。我知道有一个多项式时间算法可以做到这一点。我正在努力想出的是一个 O(|V|) 算法来做到这一点。另外，我确实意识到最大的集团可能是 4 号。

这是我一直感到困惑的地方：

在我看来，在某些时候，您需要枚举所有大小为 4 的 k 元组。但是如何在 O(|V|) 时间内完成呢？

另外值得注意的是，我曾尝试使用动态编程来解决这个问题，但我看不到如何在线性时间内做到这一点。

答案，想法，建议？

我的问题

是否有一种有效的算法可以在完整的k分图中找到最大权重（或最小权重）k-团（根据维基百科，当且仅当它们属于不同的分集时，顶点相邻的图）？

有关条款的更多详细信息

Max-weight Clique：图中的每条边都有一个权重。团的权重是团中所有边的权重之和。目标是找到一个权重最大的集团。

请注意，clique 的大小是 k，它是完整 k-partite 图中可能的最大 clique 大小。

我试过的

我在一个项目中遇到了这个问题。由于我不是 CS 人员，因此我不确定复杂性等。

我搜索了几篇相关论文，但没有一篇涉及相同的问题。我还编写了一个贪心算法+模拟退火来处理它（结果似乎不好）。我也尝试过动态编程之类的东西（但它似乎效率不高）。所以我想知道是否可以有效地计算出精确的最优值。提前致谢。

编辑由于我的输入可能非常大（例如，每个团中的顶点数是 2^k），我希望找到一个非常快速的算法（例如 k 的多项式）来计算出最佳结果。如果不可能，我们可以证明复杂性的一些下限吗？