title: Finding diameter of graph using BFS
body: <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>