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

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 tex2html_wrap_inline70808, since tex2html_wrap_inline70810 is the length of the adjacency list associated with vertex v.

This is the operation performed by the GetEdge method of the Graph interface.

enumerate all edges
In order to locate all the edges in when using adjacency matrices, it is necessary to examine all tex2html_wrap_inline70538 matrix entries. Therefore, the worst-case running time needed to enumerate all the edges is tex2html_wrap_inline70626.

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

This operation is performed using the enumerator obtained using the Edges property of the Graph interface.

enumerate edges emanating from v
To enumerate all the edges that emanate from vertex v requires a complete scan of the tex2html_wrap_inline70828 row of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is tex2html_wrap_inline70702.

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

This operation is performed using the enumerator obtained using the EmanatingEdges property of the Vertex interface.

enumerate edges incident on w
To enumerate all the edges are incident on vertex w requires a complete scan of the tex2html_wrap_inline70842 column of an adjacency matrix. Therefore, the worst-case running time when using adjacency matrices is tex2html_wrap_inline70702.

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 tex2html_wrap_inline70822.

This operation is performed using the enumerator obtained using the IncidentEdges property of the Vertex interface.

Table gif summarizes these running times.

 

 

representation scheme

operation

adjacency matrix adjacency list
find edge (v,w) O(1) tex2html_wrap_inline70808
enumerate all edges tex2html_wrap_inline70626 tex2html_wrap_inline70822
enumerate edges emanating from v tex2html_wrap_inline70702 tex2html_wrap_inline70808
enumerate edges incident on w tex2html_wrap_inline70702 tex2html_wrap_inline70822
Table: Comparison of graph representations.


next up previous contents index

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