диаметр Нахождение графа с использованием BFS

Question

Algo найти диаметр графа выглядит следующим образом:

1. Run BFS на любой arbirtray вершине и вспомнить последний узел посещаемый (скажем, т)
2. Run BFS от т и rememver последний посещенный узел (например, t ')
3. кратчайшее расстояние между t и t' будет диаметром графика.

Это то, что я узнал, и она работала хорошо, пока я не нашел следующий график:

A------G-----C------D 
| 
E------F------B 

Если я бегу BFS от A, я получаю AGECF"DB"... и BFS от B дает BFCEDGA...., so d(B,A)=3 должен быть диаметр.

Но если я бегу BFS от A в AGECF"BD" и чем запустить BFS из D, который дает DCBGFAE, d(D,E) = 4 должен быть диаметр

Что пошло не так? Разве этот алго не работает?

Answer 1

К сожалению, ваш алгоритм неверен. Посмотрите на обсуждение здесь:

https://cs.stackexchange.com/questions/194/the-time-complexity-of-finding-the-diameter-of-a-graph

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

Вы можете сделать лучше, если находитесь в направленном дереве или в других особых случаях.

Answer 2

Ваш алгоритм будет работать только в том случае, если вы хотите найти диаметр ациклического дерева. Если вы хотите найти диаметр графа, вы можете использовать алгоритм кратчайшего пути для всех пар Floyd-Warshall. Затем, перемещая всю матрицу расстояний, вы можете найти диаметр графика.