241 Computer Science Certification Practice Exam

Unlock all questions

This demo includes only 20 questions. Upgrade to access hundreds of questions, flashcards, exam simulations, and disable ads.

Full question bankExam simulationsFlashcards

From $25.99Unlock all

Session length

1 / 20

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

Diameter is the average distance between nodes; BFS runs in O(V^2) to compute all paths

Diameter is the greatest shortest-path distance between any two vertices; BFS runs in O(V+E) from a source to compute shortest paths

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.

Diameter is the total number of edges in the graph; BFS runs in O(E)

Diameter is the minimum distance between two nodes; BFS runs in O(V log V)