On Implementing Graph Representations

Abstract

The three most common graph representations, namely the adjacency matrix, one way adjacency lists and adjacency multilist, are implemented in PASCAL and their performance evaluated for twelve graphs typical to computer network configurations. We show that both adjacency multilist and one way adjacency lists are preferred over the adjacency matrix representation. Although their implementation is Slightly more complicated it out performs the latter by a factor of at least 5.