#graph-theory #breadth-first-search
#теория графов #поиск по ширине
Вопрос:
Алгоритм поиска диаметра графа выглядит следующим образом:
- Запустите BFS в любой вершине arbirtray и запомните последний посещенный узел (скажем, t)
- Запустите BFS из t и запомните последний посещенный узел (скажем, t’)
- кратчайшее расстояние между t и t’ будет диаметром графика.
Это то, что я узнал, и это работало нормально, пока я не нашел следующий график:
A------G-----C------D
|
E------F------B
Если я запускаю BFS из A , я получаю AGECF"DB"... , а BFS из B дает BFCEDGA.... , so d(B,A)=3 должен быть диаметр.
Но если я запускаю BFS из A as AGECF"BD" и затем запускаю BFS, из D которого выдает DCBGFAE , d(D,E) = 4 должен быть диаметр
Что пошло не так? Разве этот алгоритм не всегда работает?
Ответ №1:
Ваш алгоритм будет работать, только если вы хотите найти диаметр ациклического дерева. Если вы хотите найти диаметр графа, вы можете использовать алгоритм кратчайшего пути Флойда-Варшалла для всех пар. Затем, пройдя всю матрицу расстояний, вы можете найти диаметр графика.
Ответ №2:
К сожалению, ваш алгоритм неверен. Взгляните на обсуждение здесь:
https://cs.stackexchange.com/questions/194/the-time-complexity-of-finding-the-diameter-of-a-graph
В общем, если вы хотите гарантировать диаметр графа, вам нужно выполнить BFS (Дейкстра во взвешенном графике) из каждого состояния, а затем получить максимум по всем поискам. (Или вычислите информацию о кратчайшем пути для всех пар и найдите самый длинный кратчайший путь из этих данных.)
Вы можете добиться большего успеха, если вы находитесь в ориентированном дереве или в других особых случаях.