我的算法课上的作业之一是设计一种穷举搜索算法来解决派系问题。也就是说，给定尺寸图n，该算法应该确定是否存在尺寸的完整子图k。我想我已经得到了答案，但我忍不住认为它可以改进。这是我所拥有的：
版本1
input：由数组 A[0,... 表示的图n-1]，尺寸k要查找的子图。
output：如果子图存在则为 True，否则为 False
算法（类似Python的伪代码）：
def clique(A, k):
P = A x A x A //Cartesian product
for tuple in P:
if connected(tuple):
return true
return false
def connected(tuple):
unconnected = tuple
for vertex in tuple:
for test_vertex in unconnected:
if vertex is linked to test_vertex:
remove test_vertex from unconnected
if unconnected is empty:
return true
else:
return false
版本2
input：大小为 n x n 的邻接矩阵，k 为要查找的子图的大小
output：A 中大小为 k 的所有完整子图。
算法（这次是函数式/Python 伪代码）：
//Base case: return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
S = new list
for i in range(0 to n-1):
add i to S
return S
//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
C = clique(A, k-1)
S = new list
for tuple in C:
for i in range(0 to n-1):
//make sure the ith vertex is linked to each
//vertex in tuple
for j in tuple:
if A[i,j] != 1:
break
//This means that vertex i makes a clique
if j is the last element:
newtuple = (i | tuple) //make a new tuple with i added
add newtuple to S
//Return the list of k-cliques
return S
有人有什么想法、意见或建议吗？这包括我可能错过的错误以及使其更具可读性的方法（我不习惯使用太多伪代码）。
版本3
幸运的是，我在提交作业之前和我的教授谈过。当我向他展示我写的伪代码时，他微笑着告诉我，我做到了way太多工作。其一，我不必提交伪代码；我只需证明我理解这个问题。还有两个，他was想要暴力解决方案。所以我上交的内容看起来像这样：
input：图G = (V,E)，要查找的派系大小k
output: 如果派系确实存在则为 true，否则为 false
算法:
- Find the Cartesian Product Vk.
- 对于结果中的每个元组，测试每个顶点是否相互连接。如果全部连接，则返回 true 并退出。
- 返回 false 并退出。
UPDATE：添加了第二个版本。我认为这正在变得更好，尽管我没有添加任何花哨的动态编程（据我所知）。
UPDATE 2：添加了更多注释和文档，使版本 2 更具可读性。这可能就是我今天提交的版本。感谢大家的帮助！我希望我能接受多个答案，但我接受了对我帮助最大的人的答案。我会让你们知道我的教授的想法。
