Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Running Time Analysis

The breadth-first traversal enqueues each node in the graph at most once. When a node is dequeued, all the edges emanating from that node are considered. Therefore, a complete traversal enumerates every edge in the graph.

The actual running time of the breadth-first traversal method depends on the graph representation scheme used. The worst-case running time for the traversal of a graph represented using an adjacency matrix is

displaymath70938

When adjacency lists are used, the worst case running time for the breadth-first traversal method is

displaymath70939

If the graph is sparse, then tex2html_wrap_inline70636. Therefore, if a sparse graph is represented using adjacency lists and if tex2html_wrap_inline60481, the worst-case running time of the breadth-first traversal is just tex2html_wrap_inline70702.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.