Search⌘ K
AI Features
Home
Courses
A Visual Introduction to Algorithms

Analysis of breadth-first search

Explore how breadth-first search (BFS) operates on graphs by examining the time complexity of visiting vertices and edges. Understand why BFS runs in O(V+E) time and how this relates to graph connectivity and structure.

We'll cover the following...

How long does breadth-first search take for a graph with vertex set VV and edge set EE? The answer is O(V+E)O(V+E) time.

Let's see what O(V+E)O(V+E) time means. Assume for the moment that ∣E∣≥∣V∣|E| \geq |V|, which is the case for most graphs, especially those for which we run breadth-first search. Then ∣V∣+∣E∣≤∣E∣+∣E∣=2.∣E∣|V| + |E| \leq |E| + |E| = 2 . |E| ...