Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 173

Here:

(1) EDGE will be the name of the edge (if it has one).

(2) ADJ points to the location of the vertex in the Vertex File.

(3) NEXT points to the location of the next vertex in the adjacency list.

We emphasize that each edge is represented twice in the Edge File, but each record of the file corresponds to
a unique edge. The shaded area indicates that there may be other information in the record corresponding to the
edge.
Figure 8-29 shows how the graphGin Fig. 8-28(a)may appear in memory. Here the vertices ofGare
maintained in memory by a linked list using the variable START to point to the first vertex. (Alternatively, one
could use a linear array for the list of vertices, and then NEXT-V would not be required.) Note that the field
EDGE is not needed here since the edges have no name. Figure 8-29 also shows, with the arrows, the adjacency
list[D, C, A]of the vertexB.

Fig. 8-29

8.12Graph Algorithms

This section discusses two important graph algorithms which systematically examine the vertices and edges
of a graphG. One is called adepth-first search(DFS) and the other is called abreadth-first search(BFS). Other
graph algorithms will be discussed in the next chapter in connection with directed graphs. Any particular graph
algorithm may depend on the wayGis maintained in memory. Here we assumeGis maintained in memory by
its adjacency structure. Our test graphGwith its adjacency structure appears in Fig. 8-30 where we assume the
vertices are ordered alphabetically.

Fig. 8-30