What is the diameter of a graph and how does it relate to BFS complexity from a source?

Prepare for the 241 Computer Science Certification Exam with comprehensive flashcards and multiple choice questions. Enhance knowledge with explanations and hints to excel in your test journey!

The diameter of a graph is the largest distance between any two vertices, measured as the length of the shortest path between them. When you run a breadth-first search from a given source, you discover the shortest-path distance from that source to every other vertex, and you do this in time proportional to V plus E for an unweighted graph. This means you can obtain all shortest-path distances from that source efficiently, and the largest of those distances is the source’s eccentricity. Since the diameter is the maximum eccentricity across all vertices, computing it generally requires performing BFS from every vertex (to find all eccentricities) and taking their maximum, which leads to a total time of O(V*(V+E)). The option correctly states both the definition of the diameter and the single-source BFS complexity.