Hovedinnhold
Analysere bredde-først-søk
How long does breadth-first search take for a graph with vertex set and edge set ? The answer is time.
Let's see what time means. Assume for the moment that , which is the case for most graphs, especially those for which we run breadth-first search. Then . Because we ignore constant factors in asymptotic notation, we see that when , really means . If, however, we have , then , and so really means . We can put both cases together by saying that really means . In general, if we have parameters and , then really means .
(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 . A graph in which is called a free tree.)
How is it that breadth-first search runs in time? It takes time to initialize the distance and predecessor for each vertex ( time, actually). Each vertex is visited at most one time, because only the first time that it is reached is its distance time visiting vertices.
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 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.
Ønsker du å delta i samtalen?
Ingen innlegg enda.