Проблема перечисления всех элементов заданного типа в графе возникает при исследовании сетей различных видов. В статье [3], в частности, показано, каким образом алгоритмы подсчёта треугольных элементов графа могут быть использованы при определении Интернет-спама и в анализе характеристик пользователей социальной сети.Неориентированный граф G = (V, E) состоит из множества вершин V и множества связывающих их рёбер E. Одним из наиболее удобных видов представления графа является матрица смежности A, каждый элемент которой содержит число, определяющее наличие ребра между вершиной-строкой и вершиной-столбцом. Совокупность последовательно соединённых вершин графа, в которой первая и последняя вершины совпадают, называется циклом. Требуется найти алгоритм, эффективно перечисляющий все треугольники (циклы длины 3) некоторого графа.

Пример графа, содержащего треугольники:

Множество вершин V = (1, 2, 3, 4, 5, 6).
Множество рёбер E = [(1, 2), (1, 3), (2, 3), (1, 4), (3, 4), (2, 5), (3, 5), (3, 6), (4, 6), (5, 6)].

Данный граф содержит 5 треугольников, T = [(1, 2, 3), (1, 3, 4), (2, 3, 5), (3, 4, 6), (3, 5, 6)].

Три вершины a, b и c графа G образуют треугольник, если в соответствующей матрице смежности ячейки A[a, b], A[b, c] и A[a, c] одновременно не равны нулю. Все возможные тройки вершин (a, b, c) составят тогда пространство поиска решений, удовлетворяющих данному условию.

Для всех a от 0 до n:
  Для всех b от 0 до n:
    Для всех c от 0 до n:
      Если A[a, b], A[b, c] и A[a, c] не равны нулю, напечатать (a, b, c)

Данный алгоритм, однако, имеет серьёзные недостатки. При выводе результатов каждый треугольник будет повторен 6 (3! перестановок) раз, а количество проверок условия существования треугольника составит T = n^3. Для нашего графа G: T = 6^3 = 216.

Можно значительно сузить пространство поиска, перебирая комбинации троек (a, b, c), упорядоченных, например, по возрастанию(a < b < c).

Для всех a от 0 до n:
  Для всех b от a + 1 до n:
    Для всех c от b + 1 до n:
      Если A[a, b], A[b, c] и A[a, c] не равны нулю, напечатать (a, b, c)

Этот алгоритм выдаст точный результат, без дублей. Количество проверяемых комбинаций в нём равно числу сочетаний без повторений из n по 3, T = C(n, 3). Для графа G: T = 20.Пространство поиска можно сократить ещё более, заметив, что в отсутствие некоторого ребра (a, b) нет необходимости перебирать варианты в соответствующем внутреннем цикле по c.

Для всех a от 0 до n:
  Для всех b от a + 1 до n:
    Если A[a, b] = 0, переходим на следующий шаг цикла b
    Для всех c от b + 1 до n:
      Если A[b, c] и A[a, c] не равны нулю, напечатать (a, b, c)

Быстродействие данного алгоритма зависит от количества присутствующих в графе рёбер, и значение T лишь в худшем случае (матрица A состоит из одних единиц) достигает показателей предыдущего варианта. Для графа G: T = 16.Впрочем, даже такой алгоритм возможно улучшить для случая разрежённых больших графов. Чтобы это осуществить, наряду с матрицей смежности, понадобится дополнительная структура, список связи L. Номер вершины графа соответствует очередному элементу списка связи, который хранит в себе внутренний список вершин, соединённых с вершиной данного номера. Важно, что элементы списка связи упорядочены, в частности каждый следующий элемент внутреннего списка должен быть больше предыдущего, а начальный — больше соответствующего номера вершины в основном списке.

Для всех a из L:
  Для всех b из L[a]:
    Для всех c из L[b]:
      Если A[a, c] не нуль, напечатать (a, b, c)

Для графа G: T = 12.Алгоритм A отличается простотой реализации, не требует дополнительной памяти и успешно находит треугольники даже в несвязанных графах. Алгоритм B более эффективен, если есть возможность мириться с накладными расходами на создание списка связи.Ниже представлен исходный код алгоритма A на языке Python.

# Triangles enumeration algorithm(A)

def triangles(g):
    n = len(g)
    for a in range(0, n):
        for b in range(a + 1, n):
            if not g[a][b]:
                continue
            for c in range(b + 1, n):
                if g[b][c] and g[a][c]:
                    print(a + 1, b + 1, c + 1)
g = [
    [0, 1, 1, 1, 0, 0],
    [1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 1, 1],
    [1, 0, 1, 0, 0, 1],
    [0, 1, 1, 0, 0, 1],
    [0, 0, 1, 1, 1, 0]]

triangles(g)

[1]	Р. Миллер, Л. Боксер. “Последовательные и параллельные алгоритмы”. Бином. Лаборатория знаний, 2006 г.
[2]	Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. “Структуры данных и алгоритмы”. Вильямс, 2000 г.
[3]	“Semi-Streaming Algorithms for Local Triangle Counting in Massive Graphs”. http://aeolus.ceid.upatras.gr/scientific-reports/2nd_year_reports/comm.pdf