Найти треугольник на графике, используя алгоритм с конкретным временем выполнения - PullRequest
Новая
       41

Найти треугольник на графике, используя алгоритм с конкретным временем выполнения

2 голосов
/ 12 июня 2019

Мне нужно найти алгоритм, который находит треугольные циклы в неориентированном графе.Время выполнения алгоритма должно быть n ^ 2,81

Я действительно не знаю, как мне этого добиться.Было бы здорово, если бы кто-нибудь мог помочь!

Спасибо!

Ответы [ 2 ]

3 голосов
/ 12 июня 2019

Алгоритм, который вы ищете: умножение матриц . Умножьте матрицу смежности на себя три раза и найдите ненулевые элементы в главной диагонали. умножение матриц - O (N ^ 2.81): https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

EDIT:

Напомним, что в i-й строке матрицы смежности будет «1» для каждой вершины, связанной с i, то же самое относится и к столбцу.

Когда вы умножаете матрицу на себя, (M ^ 2) ij = sum (Mik * Mkj). другими словами (M ^ 2) ij - число 2-реберных путей от i до j.

Теперь, если вы снова умножите, чтобы получить M ^ 3, в каждой ячейке (M ^ 3) ij будет количество 3-реберных путей от i до j. так что в главной диагонали (M ^ 3) ii будет количество 3-краевых путей от i до i, треугольник.

0 голосов
/ 12 июня 2019

Другой способ - использовать модифицированную версию алгоритма Поиск в ширину . Попробуйте представить себе простой график, треугольник. Начните с любой вершины с BFS и сохраните, кто является родительским узлом и расстояние от корня. Всякий раз, когда вы сталкиваетесь с уже посещенной (но не законченной вершиной), которую вы можете простым серым цветом, вы должны проверить расстояние и родителя. 

   B     Start BFS from A: node A has dist=0, parent=Null
  / \                      node B has dist=1, parent=A
 /   \                     node C has dist=1, parent=A
A - - C

Например, вы сейчас находитесь на C, B его уже посетили, и A закончил (черный), теперь вы проверяете соседний с C, вы видите B и проверяете, одинаковое ли расстояние и есть ли у вас один и тот же родитель, если это правда, вы нашли треугольник, если нет, вы столкнулись с циклом, но не с треугольником.

Это будет лучше, чем O(n^2) Сложность этого алгоритма (BFS) заключается в количестве вершин + количество ребер: O(|V| + |E|).

...