Finding diameter of graph using BFS
<p>Algo to find diameter of graph is as follows:</p>

<ol>
<li>Run BFS on any arbirtray vertex and remember the last node visited (say t)  </li>
<li>Run BFS from t and rememver the last node visited (say t')  </li>
<li>shortest distance between t and t' will be the diameter of the graph.</li>
</ol>

<p>This is what I learned and it worked fine until I found the following graph:</p>

<pre><code>A------G-----C------D  
|  
E------F------B
</code></pre>

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

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

<p>What went wrong? Doesn't this algo always work?</p>