Time Comparison

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Time Comparison

The following four operations are used extensively in the implementations of many different graph algorithms:

find edge (v,w)

Given vertices v and w, this operation locates the corresponding Edge instance. When using an adjacency matrix, we can find an edge in constant time.

When adjacency lists are used, the worst-case running time is , since is the length of the adjacency list associated with vertex v.

This is the operation performed by the SelectEdge member function of the Graph class.

enumerate all edges

In order to locate all the edges in when using adjacency matrices, it is necessary to examine all

matrix entries. Therefore, the worst-case running time needed to enumerate all the edges is

On the other hand, to enumerate all the edges when using adjacency lists requires the traversal of lists. In all there are edges. Therefore the worst case running time is .

This operation is performed using the iterator returned by the Edges member function of the Graph class.

enumerate edges emanating from v

To enumerate all the edges that emanate from vertex v requires a complete scan of the

row of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is

Enumerating the edges emanating from vertex v is a trivial operation when using adjacency lists. All we need do is traverse the list. This takes time in the worst case.

This operation is performed using the iterator returned by the EmanatingEdges member function of the Graph class.

enumerate edges incident on w

To enumerate all the edges are incident on vertex w requires a complete scan of the

column of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is

Enumerating the edges incident on vertex w is a non-trivial operation when using adjacency lists. It is necessary to search every adjacency list in order to find all the edges incident on a given vertex. Therefore, the worst-case running time is .

This operation is performed using the iterator returned by the IncidentEdges member function of the Graph class.

Table

summarizes these running times.

representation scheme

operation
adjacency matrix adjacency list

find edge (v,w) O(1)

enumerate all edges

enumerate edges emanating from v

enumerate edges incident on w

Table: Comparison of Graph Representations

	representation scheme
operation	adjacency matrix	adjacency list
find edge (v,w)	O(1)
enumerate all edges
enumerate edges emanating from v
enumerate edges incident on w