проблема алгоритма

Предположим без ограничения общности, что узлы графа идентифицируются целыми числами от 0 до N-1 (без потери общности, потому что, если каждый узел должен нести другую информацию, вы можете иметь массив/вектор/список объектов N узлов, и принять эти целые числа как индексы в рассматриваемом массиве). Связность графа может быть указана, например, путем сопоставления каждого узла с набором, являющимся непосредственными соседями узла.

Для проверки соединения, а не непосредственной смежности, вам скорее понадобится другое сопоставление — переходное замыкание отображения непосредственных соседей. Конечно, для этого есть хорошие алгоритмы (см., например, исходный код Python для networkx package), но грубая сила может просто начать с копирования непосредственного сопоставления смежности в сопоставление соединения, а затем итеративно расширять наборы до тех пор, пока одна итерация не перестанет расширять какой-либо набор.

Например, пример грубой силы Python 2.6:

import copy

def transitive_closure(immediate_neighbors):
  result = copy.deepcopy(immediate_neighbors)
  changes = True
  while changes:
    changes = False
    for node in result:
      newset = set(result[node])
      for neighbor in result[node]:
        newset.update(result[neighbor])
      if newset != result[node]:
        changes = True
        result[node] = newset
  return result

immediate = {0:[1,2], 1:[0], 2:[0], 3:[4], 4:[3]}
connections = transitive_closure(immediate)
for node in sorted(connections):
  print node, sorted(connections[node])

печатает:

0 [0, 1, 2]
1 [0, 1, 2]
2 [0, 1, 2]
3 [3, 4]
4 [3, 4]

Имея под рукой словарь connections, все, что нам нужно сделать, это проверить каждую комбинацию узлов k (например, в Python 2.6 или выше itertools.combinations(range(N), k) дает нам эти комбинации): это будет клика, если это подмножество (не обязательно правильное подмножество, конечно) набора элементов, связанных с любым из его элементов.

Так, например, приведенный выше код может продолжаться, чтобы показать все 2 клика:

import itertools
cliques = set()
for somenodes in itertools.combinations(range(5), 2):
  if set(somenodes) <= connections[somenodes[0]]:
    cliques.add(somenodes)
print '%d cliques:' % len(cliques)
for c in sorted(cliques): print ' ', c

который печатает с данными, использованными в предыдущем примере:

4 cliques:
  (0, 1)
  (0, 2)
  (1, 2)
  (3, 4)

Для подходов, не использующих грубую силу, я рекомендую снова изучить исходный код networkx, на который я указывал ранее.

Хорошо, пронумеруйте вершины 1 ... n и преобразуйте граф в логическую матрицу смежности - 1 в (i, j), что означает, что i и j связаны. В неориентированном графе матрица должна быть симметричной. Теперь ваша задача сводится к поиску «подквадрата» размера k x k со всеми единицами. «Подквадрат» забавен тем, что строки и столбцы не обязательно должны быть рядом друг с другом. Чтобы получить подквадрат, вы начинаете с n строк, n столбцов, удаляете (n-k) строк и столбцов — и вуаля! ты получил это.

Теперь каждый уникальный подквадрат из всех единиц будет соответствовать клике. Чтобы проверить уникальность, представьте подквадрат в виде неизменного кортежа ((i1,j1), (i2, j2) ... (ik,jk)) (нотация Python).

В Python вы можете добавлять кортежи в неупорядоченный набор и спрашивать набор, содержит ли он уже искомый элемент.