Временная сложность нахождения диаметра графа

27

Какова временная сложность нахождения диаметра графа ?G=(V,E)

  • O(|V|2)
  • O(|V|2+|V||E|)
  • O(|V|2|E|)
  • O(|V||E|2)

Диаметр графа является максимумом множества кратчайших расстояний между всеми парами вершин графа.G

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

Gigili
источник
4
Пожалуйста, опишите немного. Почему эта проблема вас интересует? Вам нужен намек, полный анализ или ссылка? Вас интересует худшее или среднее время? Направлена ли ? G
Рафаэль
@ Рафаэль: Очевидно, мне не нужна подсказка, мне нужен полный анализ. Я все равно отредактировал свой вопрос.
Гигили
1
@Gigili Вы имеете в виду во всех случаях, верно? В противном случае все включаются в последнюю возможность (которая на общих графах равна ), что делает его правильным ответом, предполагая, что хотя бы один ответ считается правильным. Дополнительное беспокойство вызывает то, что в графе с циклами нет самого длинного пути. Что подразумевается под «самой длинной дистанцией»? O ( | V | 5 )ΘO(|V|5)
Рафаэль
@Gigili Откуда берутся четыре варианта?
Uli

Ответы:

5

Обновить:

Это решение не является правильным.

Решение, к сожалению, верно только для деревьев! Нахождение диаметра дерева даже не нужно. Вот контрпример для графиков (диаметр равен 4, алгоритм возвращает 3, если вы выберете это ):v

введите описание изображения здесь


Если график направлен, то это довольно сложно, вот статья, в которой утверждается, что в плотном случае результаты быстрее, чем использование алгоритмов для всех пар кратчайших путей.

Тем не менее, моя главная мысль о том, что график не направлен, и с неотрицательными весами я слышал о хорошем трюке несколько раз:

  1. Выберите вершинуv
  2. Найти такой , что является максимальнымд ( V , U )ud(v,u)
  3. Найти такое, что максимальноd ( u , w )wd(u,w)
  4. Вернутьd(u,w)

Его сложность такая же, как два последовательных поиска в ширину ¹, то есть если граф связан ².O(|E|)

Это казалось фольклорным, но сейчас я все еще пытаюсь получить справку или доказать ее исправление. Я обновлю, когда я достигну одной из этих целей. Это кажется таким простым, я отправляю свой ответ прямо сейчас, возможно, кто-то получит его быстрее.

¹ если график весовой, в википедии, кажется, написано но я уверен только в .O ( | E | log | V | )O(|E|+|V|log|V|)O(|E|log|V|)

² Если график не связан, вы получите но вам, возможно, придется добавить чтобы выбрать один элемент из каждого подключенного компонента. Я не уверен, если это необходимо, и в любом случае, вы можете решить, что диаметр в этом случае бесконечен.O ( α ( | V | ) )O(|V|+|E|)O(α(|V|))

jmad
источник
Для работы Dijsktra в указанный промежуток времени необходимо использовать кучи Фибоначчи, а не обычную реализацию.
Суреш
8
Это очень неправильный ответ, этот алгоритм фольклорный, но на деревьях не общие графы. PS: я вижу ваш встречный пример, но это не очень хороший ответ, чтобы быть отмеченным как ответ.
У меня два вопроса о неправильном решении. 1. Даст ли это хотя бы диапазон, в котором должен быть правильный ответ? Например, если метод находит диаметр d , будет ли правильное решение между d и 2d ? 2. Что произойдет, если мы добавим еще одно косвенное обращение и рассмотрим все узлы, найденные косвенным обращением (а не только один)? Тогда встречный пример, приведенный в посте, сработает, поскольку истинные периферийные вершины находятся среди узлов, найденных вторым косвением.
Мафу
32

Я предполагаю , что вы имеете в виду диаметр из , который является самым длинным кратчайший путь найден в .GGG

Найти диаметр можно, сначала найдя все пары кратчайших путей и определив максимальную найденную длину. Алгоритм Флойда-Варшалла делает это во время . Алгоритм Джонсона может быть реализован для достижения времени .O ( | V | 2 log | V | + | V || E | )Θ(|V|3)O(|V|2log|V|+|V||E|)

Меньшая граница времени выполнения в худшем случае кажется труднодостижимой, поскольку существуют расстояния необходимо учитывать, и рассчитывать эти расстояния в сублинейное (амортизированное) время, каждое из которых будет непростым; см. здесь для связанной границы. Обратите внимание на этот документ, который использует другой подход и получает (немного) более быстрый алгоритм.O(|V|2)

Рафаэль
источник
2
Если вы получили деньги за эти документы, проверьте Google Scholar.
Рафаэль
Также это исключение стоит отметить для неориентированных деревьев , где вы можете получить диам. только с одним обходом DFS.
Азам
15

Вы также можете рассмотреть теоретический подход алгебраического графа. Диаметр - это наименьшее целое число матрица обладает тем свойством, что все записи в отличны от нуля. Вы можете найти по итераций умножения матриц. Алгоритм диаметра тогда требует времени , где является пределом для умножения матрицы. Например, при обобщении алгоритма Копперсмита-Винограда Василевской Уильямс алгоритм диаметра будет работать в . Для быстрого ознакомления см. Главу 3 в книге Фан Чунга здесь .t M = I + A M t t O ( log n ) O ( M ( n ) log n ) M ( n ) O ( n 2,3727 log n )diam(G)tM=I+AMttO(logn)O(M(n)logn)M(n)O(n2.3727logn)

Если вы ограничите свое внимание подходящим классом графов, вы сможете решить задачу APSP за оптимальное время . Эти классы включают в себя как минимум интервальные графы, круговые дуговые графы, графы перестановок, двудольные графы перестановок, сильно хордовые графы, хордальные двудольные графы, дистанционно-наследственные графы и двудольные хордовые графы. Например, см. Dragan, FF (2005). Оценка всех пар кратчайших путей в семействах ограниченных графов: унифицированный подход. Журнал Алгоритмы, 57 (1), 1-21 и ссылки в нем.O(n2)

Юхо
источник
2
Стоит отметить, что этот алгоритм работает только в невзвешенном случае.
GMB
-2

Допущения:
1. График невзвешенный
2. График направлен

O (| V || E |) сложность времени.

Алгоритм:

ComputeDiameter(G(V,E)):
  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

Пояснение:
мы проверяем цикл. если граф содержит цикл, то мы продолжаем двигаться в цикле, поэтому у нас будет бесконечное расстояние. Мы проверяем на связность. Если граф не связен, это означает вершину u из G1 в вершину v в G2. Где G1 и G2 - любые два подграфа, которые не связаны. Так что у нас снова будет бесконечное расстояние. Мы будем использовать BFS для вычисления максимального расстояния между данным узлом (u) и всеми другими узлами (v), которые достижимы из u. Затем мы возьмем максимум из ранее вычисленного диаметра и результат, возвращаемый BFS. Таким образом, у нас будет текущий максимальный диаметр.

Время выполнения анализа:

  1. O (| E |) с использованием DFS
  2. O (| E |) с использованием DFS
  3. BFS запускается за O (| E |) время.
  4. Мы должны вызвать функцию BFS для каждой вершины, так что всего это займет O (| V || E |) времени.

Общее время = O (| v || E |) + O (| E |) + O (| E |),
поскольку | V || E | > | E |
таким образом, у нас есть время выполнения как O (| v || E |).

BFS
DFS

Примечание: это не элегантное решение этой проблемы.

sonus21
источник
Ациклические связные графы - это деревья, для которых задача проще (потому что диаметр задается самым длинным путем). Это было рассмотрено здесь и здесь , где приведены более быстрые алгоритмы. (Одного рекурсивного обхода или, альтернативно, двух BFS достаточно.)
Рафаэль
1
@ Рафаэль Нет, ациклические неориентированные графы - это деревья. DAG - это DAG.
Дэвид Ричерби,
@DavidRicherby Верно. (Хотя, технически, ответ не говорит, исключает ли он направленный или ненаправленный цикл.;)) В любом случае, это не что иное, как решение APSPP (наивный подход), который уже был рассмотрен для общего случая предыдущими ответами.
Рафаэль
@ Рафаэль Вы уверены, что ациклические графы - это деревья? Граф ацикличен, это не значит, что граф всегда будет деревом. Дерево - это всего лишь частный случай этого. Также это прямой алгоритм и сложность времени O (| V || E |).
sonus21
Да, я уверен. (Может быть, вы думаете о корневых деревьях, которые имеют другой вкус.)
Рафаэль