Graphs - Data Structures and Algorithm Analysis - page 378

It is reasonably straightforward to implement our graph and edge ADTs using
either the adjacency list or adjacency matrix. The sample implementations pre-
sented here do not address the issue of how the graph is actually created. The user
of these implementations must add functionality for this purpose, perhaps reading
the graph description from a file. The graph can be built up by using the setEdge
function provided by the ADT.
Figure 11.6 shows an implementation for the adjacency matrix. Array Mark
stores the information manipulated by the setMark and getMark functions. The
edge matrix is implemented as an integer array of size nn for a graph of n ver-
tices. Position (i, j) in the matrix stores the weight for edge (i, j) if it exists. A
weight of zero for edge (i, j) is used to indicate that no edge connects Vertices i
and j.
Given a vertex V, function first locates the position in matrix of the first
edge (if any) of V by beginning with edge (V, 0) and scanning through row V until
an edge is found. If no edge is incident on V, then first returns n.
Function next locates the edge following edge (i, j) (if any) by continuing
down the row of Vertex i starting at position j + 1, looking for an edge. If no
such edge exists, next returns n. Functions setEdge and delEdge adjust the
appropriate value in the array. Function weight returns the value stored in the
appropriate position in the array.
Figure 11.7 presents an implementation of the adjacency list representation for
graphs. Its main data structure is an array of linked lists, one linked list for each
vertex. These linked lists store objects of type Edge , which merely stores the index
for the vertex pointed to by the edge, along with the weight of the edge.
/ ** EdgeclassforAdjacencyListgraphrepresentation * /
classEdge{
privateintvert,wt;
publicEdge(intv,intw)//Constructor
{vert=v;wt=w;}
publicintvertex(){returnvert;}
publicintweight(){returnwt;}
}
Implementation for Graphl member functions is straightforward in principle,
with the key functions being setEdge , delEdge , and weight . They simply
start at the beginning of the adjacency list and move along it until the desired vertex
has been found. Note that isEdge checks to see if j is already the current neighbor
in i's adjacency list, since this will often be true when processing the neighbors of
each vertex in turn.