Вот упражнение в Руководстве по разработке алгоритмов.
Рассмотрим задачу определения, является ли заданный неориентированный граф G = (V, E) содержит треугольник или цикл длины 3.
(a) Дайте O (| V | ^ 3), чтобы найти треугольник, если он существует.
(b) Улучшить ваш алгоритм работает во времени O (| V | · | E |). Вы можете предположить | V | ≤ | E |.
Обратите внимание, что эти границы дают вам время для преобразования между матрица смежности и представления списка смежности G.
Вот мои мысли:
(a) Если граф задан как список смежности, я могу преобразовать список в матрицу через O (| V | ^ 2). то я делаю:
for (int i = 0;i < n;i++)
for (int j = i+1;j < n;j++)
if (matrix[i][j] == 1)
for (int k = j+1;k < n;k++)
if (matrix[i][k] == 1 && matrix[j][k] == 1)
return true;
Это должно дать O (| V | ^ 3), чтобы проверить треугольник.
(б) Мое первое интуитивное заключается в том, что если граф задан как список смежности, тогда я сделаю bfs. Всякий раз, когда найден перекрестный край, например, if y-x is a cross edge
, тогда я будет check whether parent[y] == parent[x], if true, then a triangle is found
.
Может ли кто-нибудь сказать мне, правильно ли мое мышление или нет?
Также для этого (б) я не уверен в его сложности. Должно ли это быть O (| V | + | E |), правильно?
Как я могу сделать это в O (| V | * | E |)?