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?