1
$\begingroup$

I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a graph. The students were told they wouldn't be graded for efficiency, so the expected answer was a brute force algorithm where they ran BFS from every node to every other node and returned the maximum distance from these BFS runs. The students were provided with a BFS method they could reference in their pseudocode which took as an input a node and returned two mappings: one from each node in the graph to its distance from the start node (called distmap), and one from each node to its 'parent node' along the shortest path from the input node (called parentmap).

One student wrote the following algorithm:

1. Choice an arbitrary node from the graph and run BFS from it.
2. Create a set Temp of all the nodes that are not values in parentmap (ie nodes which don't lie upon any shortest paths)
3. Initialize max_dist to 0
4. For each node n in Temp:
    5. Run BFS from n
    6. For each value d in distmap:
        7. IF d > max_dist THEN set max_dist equal to d
8. RETURN max_dist

I believe this answer is correct, but I am unable to prove it. Can someone prove why it works or provide a counterexample?

$\endgroup$
3
$\begingroup$

It works for trees (although it can be simplified). However, on general graphs it does not work.

If your arbitrary vertex $v$ is the one on the top (labeled 1), then the Temp={8,9}. However, the unique diameter path is from 7 to 6.

A graph on 9 vertices

$\endgroup$
  • $\begingroup$ Maybe not the proper place for bug reports, but Grapher seems to compute correctly the diameter $d$, but it outputs $d+1$. For instance, it tells you that a complete graph has diameter 2 (but it should be 1). $\endgroup$ – Juho Jun 3 '17 at 15:31
  • $\begingroup$ @Juho duly noted, it returns the number of vertices in the diameter rather than the length of the path due to the author's obsessions with the path notation $P_4$ meaning a path of length 3 and various misunderstandings and confusions. It should be fixed, along with much else in the app. $\endgroup$ – Pål GD Jun 4 '17 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.