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

226 DIRECTED GRAPHS [CHAP. 9

(a) Since START=3, the list begins with the vertexB. Then NEXT-V tells us to go to 1(D), then 7(C), then 8(E),

then 4(F ), and then 5(A); that is,

B, D, C, E, F, A

(b) Here succ(A)=[ 1 (D), 4 (F ), 3 (B)]=[D, F, B]. Specifically, PTR[5(A)]=6 and END-V[6]= 1 (D)tells

us that succ(A)begins withD. Then NEXT-E[6]=2 and END-V[2]= 4 (F )tells us thatFis the next vertex

in succ(A). Then NEXT-E[2]=5 and END-V[5]=3(B)tells us thatBis the next vertex in succ(A). However,

NEXT-E[5]=0 tells us that there are no more successors ofA. Similarly,

succ(B)=[C, D], succ(C)=[E], succ(D)=[E], succ(E)=[D]

Furthermore succ(F )=
, since PTR[4(F )]=0. In other words,

G=[A:D, F, B; B:C, D; C:E; D:E; E:D; F:
]

(c) Use the successor lists obtained in (b) and the weights of the edges in the Edge File in Fig. 9-25(a) to draw the

graph in Fig. 9-25(b).

9.12. Suppose Friendly Airways has nine daily flights as follows:

103 Atlanta to Houston 203 Boston to Denver 305 Chicago to Miami

106 Houston to Atlanta 204 Denver to Boston 308 Miami to Boston

201 Boston to Chicago 301 Denver to Reno 401 Reno to Chicago

Describe the data by means of a labeled directed graphG.

The data are described by the graph in Fig. 9-26(a) (where the flight numbers have been omitted for notational

convenience.)

Fig. 9-26

9.13. Describe how the graph in Problem 9.12 may appear in memory using a linked representation where the

cities and flights appear in linear sorted arrays.

See Fig. 9-26(b) (whereA,B,...denote, respectively, Atlanta, Boston,...). There is no need for a START variable

since the cities form an array, not a linked list. We also use ORIG (origin) and DEST (destination) instead of BEG-V

and END-V.

9.14. Clearly, the data in Problem 9.12 may be efficiently stored in a file where each record contains only three

fields:

Flight Number, City of Origin, City of Destination