next up previous contents index Search
Next: 0.4.2 Graph Traversal Up: 0.4 Graph Algorithms Previous: 0.4 Graph Algorithms

0.4.1 Graph Representation

It is possible to represent graphs in computer memory with a variety of different data structures. One strategy is to use an adjacency matrix. An adjacency matrix is a     two dimensional array in which the row and column headers represent different vertexes in the graph. A one-way edge between, for example, vertex one and three, is denoted by a positive value in array position (1, 3). In a weighted graph the value stored in each array location corresponds to the weight or cost of each particular edge. If an edge is bi-directional it has two entries in the matrix. One entry represents the (source, destination) route while the other handles the (destination, source) return route.

Another method for representing graphs is as a more complicated linked list structure. Each vertex in   the graph is a node in a master linked list. Another linked list emanates from each vertex node and denotes the vertexes directly adjacent to a given source vertex. This method, often called an adjacency list, is more space efficient than the adjacency matrix for graphs which do not have very many edges (so-called sparce graphs).        

Scott Gasch