|
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).
|
Search