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