一个在我的算法类中的任务是设计一个详尽的搜索算法，解决了团问题。也就是说，给定大小的曲线图的 N 的，该算法应该确定是否存在一个完整的子图的尺寸的 K 的。我想我已经得到了答案，但我不能不认为这还有待改进。这是我有：

One of the assignments in my algorithms class is to design an exhaustive search algorithm to solve the clique problem. That is, given a graph of size n, the algorithm is supposed to determine if there is a complete sub-graph of size k. I think I've gotten the answer, but I can't help but think it could be improved. Here's what I have:

输入：再由数组A psented $ P $ A图[0，... N 的-1]，大小的 K 子图中找到。

input: A graph represented by an array A[0,...n-1], the size k of the subgraph to find.

输出：如果一个子图存在，否则返回False

output: True if a subgraph exists, False otherwise

算法（在蟒蛇般的伪code）：

Algorithm (in python-like pseudocode):

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版

输入：大小为n的邻接矩阵为n，和k子图的大小，找到

Version 2

input: An adjacency matrix of size n by n, and k the size of the subgraph to find

输出：所有的完整子图在一个大小为k

output: All complete subgraphs in A of size k.

算法（这次是在功能/ Python的伪code）：

Algorithm (this time in functional/Python pseudocode):

//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

没有任何人有任何想法，意见或建议？这包括错误我可能会错过，以及如何使这个更具可读性（我不习惯用多少伪code）。

Does anybody have any thoughts, comments, or suggestions? This includes bugs I might have missed as well as ways to make this more readable (I'm not used to using much pseudocode).

幸运的是，我跟我的教授提交转让前。当我给他看了伪code我写了，他笑着对我说，我做的办法的工作太多了。首先，我没有提交假code;我只是要证明我理解这个问题。其二，他的是的希望蛮力解决方案。因此，我转身看起来是这样的：

Fortunately, I talked to my professor before submitting the assignment. When I showed him the pseudo-code I had written, he smiled and told me that I did way too much work. For one, I didn't have to submit pseudo-code; I just had to demonstrate that I understood the problem. And two, he was wanting the brute force solution. So what I turned in looked something like this:

输入：图G =（V，E），该集团的规模找的 K 的

input: A graph G = (V,E), the size of the clique to find k

输出：如果一个集团确实存在，否则为false

output: True if a clique does exist, false otherwise

算法

找到笛卡尔商品V K 。 对于结果的每个元组，测试是否每个顶点连接到每个其他。如果所有的连接，返回true和退出。 返回FALSE并退出。

更新：添加第二个版本。我认为这是越来越好，虽然我还没有添加任何花哨的动态规划（据我所知）。

UPDATE: Added second version. I think this is getting better although I haven't added any fancy dynamic programming (that I know of).

更新2 ：增加了一些更多的评论和文件，使第2版更具可读性。这可能是我把今天的版本。感谢大家的帮助！我希望我能接受一个以上的答案，但我接受了答案由帮助我出了大部分人。我会让你们知道我的教授认为。

UPDATE 2: Added some more commenting and documentation to make version 2 more readable. This will probably be the version I turn in today. Thanks for everyone's help! I wish I could accept more than one answer, but I accepted the answer by the person that's helped me out the most. I'll let you guys know what my professor thinks.

推荐答案

一些评论：

您只需要考虑正选择-k个顶点的组合，不是所有的k元组（N ^ķ人）。 连接（元组）不看的权利。难道你需要重新设置悬空循环中？ 正如其他人所说，也有暴力破解这更好的方式。考虑以下递归关系式：A（K + 1）-subgraph是一个集团如果第一k个顶点形成一个集团和顶点第（k + 1）是相邻的第k个顶点的。您可以在两个方向上应用此： 在开始用1 - 集团逐渐扩大的集团，直到你得到所需的大小。例如，如果m是在当前集团最大顶点，尝试添加顶点{M + 1，M + 2，...，N-1}得到一个集团是一个顶点大。 （这类似于一个深度优先遍历树，其中树节点的子节点比当前集团最大顶点较大的顶点。） 先从所需大小的子图，并检查它是否是一个集团，利用递推关系。设置记忆化表来存储结果一路走来。 You only need to consider n-choose-k combinations of vertices, not all k-tuples (n^k of them). connected(tuple) doesn't look right. Don't you need to reset unconnected inside the loop? As the others have suggested, there are better ways of brute-forcing this. Consider the following recursive relation: A (k+1)-subgraph is a clique if the first k vertices form a clique and vertex (k+1) is adjacent to each of the first k vertices. You can apply this in two directions: Start with a 1-clique and gradually expand the clique until you get the desired size. For example, if m is the largest vertex in the current clique, try to add vertex {m+1, m+2, ..., n-1} to get a clique that is one vertex larger. (This is similar to a depth-first tree traversal, where the children of a tree node are the vertices larger than the largest vertex in the current clique.) Start with a subgraph of the desired size and check if it is a clique, using the recursive relation. Set up a memoization table to store results along the way.