CHAP. 9] DIRECTED GRAPHS 213
Figure 9-10 shows how the graphGin Fig. 9-9(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.) The choice of eight
locations for the Vertex File and 10 locations for the Edge File is arbitrary. The additional space in the files will be
used if additional vertices or edges are inserted in the graph. Figure 9-10 also shows, with arrows, the adjacency
list [B, C, D] of the vertexA.
Fig. 9-109.8Graph Algorithms: Depth-First and Breadth-First Searches
This section discusses two important graph algorithms for a given graphG. 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. 9-11.
Many applications of graphs require one to systematically examine the vertices and edges of a graphG. There
are two standard ways that this is done. One way is called adepth-first search(DFS) and the other is called a
breadth-first search(BFS). (These algorithms are essentially identical to the analogous algorithms for undirected
graphs in Chapter 8.)
Fig. 9-11