Разработка алгоритма задачи клики

Одно из заданий в моем классе алгоритмов - разработать исчерпывающий алгоритм поиска для решения проблемы клики. То есть, учитывая график размера n, алгоритм должен определить, существует ли полный подграф размера k. Я думаю, что получил ответ, но я не могу не думать, что его можно улучшить. Вот что у меня есть:

Версия 1

input: график, представленный массивом A [0,... n-1], размер k подграфа для поиска.

вывод: 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 на n, а k - размер подграфа, чтобы найти

output: все полные подграфы в размера 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

К счастью, я поговорил с моим профессором, прежде чем отправить задание. Когда я показал ему псевдокод, который я написал, он улыбнулся и сказал мне, что я слишком много работал. Во-первых, мне не нужно было вводить псевдокод; Мне просто нужно было продемонстрировать, что я понял проблему. И два, он хотел решения грубой силы. Так что я повернулся, выглядел примерно так:

input: граф G = (V, E), размер клики, чтобы найти k

output: True, если клика существует, false в противном случае

Алгоритм

• Найти декартово произведение V ^k.
• Для каждого кортежа в результате проверьте, подключена ли каждая вершина ко всем другим. Если все подключены, верните true и выйдите.
• Вернуть false и выйти.

ОБНОВЛЕНИЕ. Добавлена ​​вторая версия. Я думаю, что это становится все лучше, хотя я не добавил никаких фантастических динамических программ (что я знаю).

ОБНОВЛЕНИЕ 2: добавлено несколько комментариев и документации, чтобы сделать версию 2 более удобочитаемой. Вероятно, это версия, в которую я перехожу сегодня. Спасибо за помощь! Хотел бы я принять более одного ответа, но я принял ответ от человека, который помог мне больше всего. Я дам вам понять, что думает мой профессор.

Ответы

P = A x A x A  //Cartesian product