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

CHAP. 8] GRAPH THEORY 189

Fig. 8-56

(b) During the DFS algorithm, the first vertexNin STACK is processed and the neighbors ofN(which have not been

previously processed) are then pushed onto STACK. Initially, the beginning vertexAis pushed onto STACK. The

following shows the sequence of waiting lists in STACK and the vertices being processed:

STACK ADCBKCBLJCBMJCBJCBCBB


Vertex AD K L M J C B

In other words the vertices are processed in the order:A,D,K,L,M,J,C,B.

8.30. Repeat Problem 8.29 for the graphGin Fig. 8-56(b).

(a) List the neighbors of each vertex as follows:

G=[A:B, C, D; B:A; C:A, K, L; D:A; J:K, M; K:C, J, M; L:C, M; M:J, K, L]

(b) The following shows the sequence of waiting lists in STACK and the vertices being processed:

STACK A DCB CB LKB MKB KJB JB B 


Vertex AD C L M K J B

In other words the vertices are processed in the order:A, D, C, L, M, K, J, B.

8.31. Beginning at vertexAand using a BFS (breadth-first search) algorithm, find the order the vertices are

processed for the graphG:(a) in Fig. 8-56(a),(b) in Fig. 8-56(b).

(a) The adjacency structure ofGappears in Problem 8.29. During the BFS algorithm, the first vertexNin QUEUE

is processed and the neighbors ofN(which have not appeared previously) are then added onto QUEUE. Initially,

the beginning vertexAis assigned to QUEUE. The following shows the sequence of waiting lists in QUEUE and

the vertices being processed:

QUEUE ADCBJDCJDKJMKLML


Vertex AB C D J K M L

In other words the vertices are processed in the order:A,B,C,D,J,K,M,L.