CODEWITHSUNDEEP
graph-theorybreadth-first-search
Nitesh Methani
Nitesh Methani

Reputation: 1

Finding diameter of graph using BFS

Algo to find diameter of graph is as follows:

  1. Run BFS on any arbirtray vertex and remember the last node visited (say t)
  2. Run BFS from t and rememver the last node visited (say t')
  3. shortest distance between t and t' will be the diameter of the graph.

This is what I learned and it worked fine until I found the following graph:

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

If I run BFS from A, I get AGECF"DB"..., and BFS from B gives BFCEDGA...., so d(B,A)=3 should be the diameter.

But if I run BFS from A as AGECF"BD" and than run BFS from D which gives DCBGFAE, d(D,E) = 4 should be the diameter

What went wrong? Doesn't this algo always work?

Upvotes: 0

Views: 13906

Answers (2)

Bakhtiar Hasan
Bakhtiar Hasan

Reputation: 899

Your algorithm will work only if you want to find diameter of an acyclic tree. If you want to find diameter of a graph, you can use Floyd-Warshall's all pair shortest path algorithm. Then traversing the whole distance matrix, you can find diameter of the graph.

Upvotes: 3

Nathan S.
Nathan S.

Reputation: 5388

Unfortunately your algorithm is incorrect. Take a look at the discussion here:

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

In general, if you want to guarantee the diameter of a graph you need to do a BFS (Dijkstra in a weighted graph) from every state and then take the maximum over all searches. (Or compute the all-pairs shortest-path information and find the longest shortest path from that data.)

You can do better if you are in a directed tree, or in other special cases.

Upvotes: 1

Related Questions