Finding Durchmesser von Graphen BFS mit

Question

Algo Durchmesser von Graphen zu finden ist wie folgt:

1. Run BFS auf jedem arbirtray Vertex und erinnere mich an den letzten Knoten besucht (sagen t)
2. Run BFS von t und denke daran, der letzte besuchte Knoten (zB t ')
3. Der kürzeste Abstand zwischen t und t' ist der Durchmesser des Graphen.

Das ist, was ich gelernt und es funktionierte gut, bis ich die folgende Grafik gefunden:

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

Wenn ich BFS von A, ich AGECF"DB"... laufen zu bekommen, und BFS von B gibt BFCEDGA.... sollte so d(B,A)=3 sein der Durchmesser.

Aber wenn ich laufen BFS von A als AGECF"BD" und als BFS laufen von D die DCBGFAE gibt, d(D,E) = 4 sollte der Durchmesser

sein, was falsch gelaufen? Funktioniert dieser Algo nicht immer?

Answer 1

Leider ist Ihr Algorithmus falsch. Werfen Sie einen Blick auf die Diskussion hier:

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

Im Allgemeinen, wenn Sie den Durchmesser eines Graphen gewährleisten möchten, dass Sie benötigen einen BFS (Dijkstra in einem gewichteten Graphen) zu tun, von jedem Staat und dann nehmen die Maximum über alle Suchen. (Oder berechnen Sie die kürzesten Pfadinformationen für alle Paare und suchen Sie den längsten kürzesten Pfad aus diesen Daten.)

Sie können es besser machen, wenn Sie sich in einem gerichteten Baum oder in anderen speziellen Fällen befinden.

Answer 2

Ihr Algorithmus funktioniert nur, wenn Sie den Durchmesser eines azyklischen Baumes finden möchten. Wenn Sie den Durchmesser eines Diagramms finden möchten, können Sie den Algorithmus für den kürzesten Pfad des Paares Floyd-Warshall verwenden. Wenn Sie dann die ganze Entfernungsmatrix durchlaufen, können Sie den Durchmesser des Graphen finden.