Какова временная сложность нахождения диаметра графа ?
Диаметр графа является максимумом множества кратчайших расстояний между всеми парами вершин графа.
Я понятия не имею, что с этим делать, мне нужен полный анализ того, как решить проблему, подобную этой.
Ответы:
Обновить:
Это решение не является правильным.
Решение, к сожалению, верно только для деревьев! Нахождение диаметра дерева даже не нужно. Вот контрпример для графиков (диаметр равен 4, алгоритм возвращает 3, если вы выберете это ):v
Если график направлен, то это довольно сложно, вот статья, в которой утверждается, что в плотном случае результаты быстрее, чем использование алгоритмов для всех пар кратчайших путей.
Тем не менее, моя главная мысль о том, что график не направлен, и с неотрицательными весами я слышал о хорошем трюке несколько раз:
Его сложность такая же, как два последовательных поиска в ширину ¹, то есть если граф связан ².O ( | E| )
Это казалось фольклорным, но сейчас я все еще пытаюсь получить справку или доказать ее исправление. Я обновлю, когда я достигну одной из этих целей. Это кажется таким простым, я отправляю свой ответ прямо сейчас, возможно, кто-то получит его быстрее.
¹ если график весовой, в википедии, кажется, написано но я уверен только в .O ( | E | log | V | )O ( | E| + | В| журнал| В| ) O ( | E| журнал| В| )
² Если график не связан, вы получите но вам, возможно, придется добавить чтобы выбрать один элемент из каждого подключенного компонента. Я не уверен, если это необходимо, и в любом случае, вы можете решить, что диаметр в этом случае бесконечен.O ( α ( | V | ) )O(|V|+|E|) O(α(|V|))
источник
Я предполагаю , что вы имеете в виду диаметр из , который является самым длинным кратчайший путь найден в .GG G
Найти диаметр можно, сначала найдя все пары кратчайших путей и определив максимальную найденную длину. Алгоритм Флойда-Варшалла делает это во время . Алгоритм Джонсона может быть реализован для достижения времени .O ( | V | 2 log | V | + | V | ⋅ | E | )Θ(|V|3) O(|V|2log|V|+|V|⋅|E|)
Меньшая граница времени выполнения в худшем случае кажется труднодостижимой, поскольку существуют расстояния необходимо учитывать, и рассчитывать эти расстояния в сублинейное (амортизированное) время, каждое из которых будет непростым; см. здесь для связанной границы. Обратите внимание на этот документ, который использует другой подход и получает (немного) более быстрый алгоритм.O(|V|2)
источник
Вы также можете рассмотреть теоретический подход алгебраического графа. Диаметр - это наименьшее целое число матрица обладает тем свойством, что все записи в отличны от нуля. Вы можете найти по итераций умножения матриц. Алгоритм диаметра тогда требует времени , где является пределом для умножения матрицы. Например, при обобщении алгоритма Копперсмита-Винограда Василевской Уильямс алгоритм диаметра будет работать в . Для быстрого ознакомления см. Главу 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) t M=I+A Mt t O(logn) O(M(n)logn) M(n) O(n2.3727logn)
Если вы ограничите свое внимание подходящим классом графов, вы сможете решить задачу APSP за оптимальное время . Эти классы включают в себя как минимум интервальные графы, круговые дуговые графы, графы перестановок, двудольные графы перестановок, сильно хордовые графы, хордальные двудольные графы, дистанционно-наследственные графы и двудольные хордовые графы. Например, см. Dragan, FF (2005). Оценка всех пар кратчайших путей в семействах ограниченных графов: унифицированный подход. Журнал Алгоритмы, 57 (1), 1-21 и ссылки в нем.O(n2)
источник
Допущения:
1. График невзвешенный
2. График направлен
O (| V || E |) сложность времени.
Алгоритм:
Пояснение:
мы проверяем цикл. если граф содержит цикл, то мы продолжаем двигаться в цикле, поэтому у нас будет бесконечное расстояние. Мы проверяем на связность. Если граф не связен, это означает вершину u из G1 в вершину v в G2. Где G1 и G2 - любые два подграфа, которые не связаны. Так что у нас снова будет бесконечное расстояние. Мы будем использовать BFS для вычисления максимального расстояния между данным узлом (u) и всеми другими узлами (v), которые достижимы из u. Затем мы возьмем максимум из ранее вычисленного диаметра и результат, возвращаемый BFS. Таким образом, у нас будет текущий максимальный диаметр.
Время выполнения анализа:
Общее время = O (| v || E |) + O (| E |) + O (| E |),
поскольку | V || E | > | E |
таким образом, у нас есть время выполнения как O (| v || E |).
BFS
DFS
Примечание: это не элегантное решение этой проблемы.
источник