Analysere bredde-først-søk

How long does breadth-first search take for a graph with vertex set V and edge set E? The answer is O, left parenthesis, V, plus, E, right parenthesis time.
Let's see what O, left parenthesis, V, plus, E, right parenthesis time means. Assume for the moment that vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, which is the case for most graphs, especially those for which we run breadth-first search. Then vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar. Because we ignore constant factors in asymptotic notation, we see that when vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, O, left parenthesis, V, plus, E, right parenthesis really means O, left parenthesis, E, right parenthesis. If, however, we have vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, then vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar, and so O, left parenthesis, V, plus, E, right parenthesis really means O, left parenthesis, V, right parenthesis. We can put both cases together by saying that O, left parenthesis, V, plus, E, right parenthesis really means O(max(V,E)) O(\max(V,E)) . In general, if we have parameters x and y, then O, left parenthesis, x, plus, y, right parenthesis really means O(max(x,y)) O(\max(x,y)) .
(Note, by the way, that a graph is connected if there is a path from every vertex to all other vertices. The minimum number of edges that a graph can have and still be connected is vertical bar, V, vertical bar, minus, 1. A graph in which vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 is called a free tree.)
How is it that breadth-first search runs in O, left parenthesis, V, plus, E, right parenthesis time? It takes O, left parenthesis, V, right parenthesis time to initialize the distance and predecessor for each vertex (Θ(V) \Theta(V) time, actually). Each vertex is visited at most one time, because only the first time that it is reached is its distance null, and so each vertex is enqueued at most one time. Since we examine the edges incident on a vertex only when we visit from it, each edge is examined at most twice, once for each of the vertices it's incident on. Thus, breadth-first search spends O, left parenthesis, V, plus, E, right parenthesis time visiting vertices.

This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.