16) Apply the Breadth-first Search Algorithm to find a path from 1 to 3 in Figure...

Transcribed Image Text:

16) Apply the Breadth-first Search Algorithm to find a path from 1 to 3 in Figure 3. What would be the final value of V (an example of V is shown in Table 1 below, where Depthset is equal to the number of edges used in the path starting at 1 and ending at k)? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order. Algorithm 9.3.2: Breadth-first Search A broadcasting algorithm for finding a path between vertex i and vertex jo a graph having n vertices. Each item V, of a list V = (V, V,..., V], consists of a Boclean field V. found and an integer field V. from. The sets D, D2,..., caled depth sets, have the property that if D., then the shortest path from vertex i to vertex & is of length r. In Step 5, a stack is used to pu: the vertex list for the path from the vertex i to vertex ; in the proper ordes That stack is the output of the algorithm. 1. Set the value V-found equal to False, k = 1, 2,..., 2. 3. D, 0 {i} 4. while (-V. found) and (D,) Dri- for each k in D: for each edye (kl). If V. found False: V. found True V.from-k Dr+1 = Dr+1 U{t} 5. If V. found: S = EmptyStack ok=j while V.from: Push & onto S k= V. from Push konto S Push onto 3 16) Apply the Breadth-first Search Algorithm to find a path from 1 to 3 in Figure 3. What would be the final value of V (an example of V is shown in Table 1 below, where Depthset is equal to the number of edges used in the path starting at 1 and ending at k)? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order. Algorithm 9.3.2: Breadth-first Search A broadcasting algorithm for finding a path between vertex i and vertex jo a graph having n vertices. Each item V, of a list V = (V, V,..., V], consists of a Boclean field V. found and an integer field V. from. The sets D, D2,..., caled depth sets, have the property that if D., then the shortest path from vertex i to vertex & is of length r. In Step 5, a stack is used to pu: the vertex list for the path from the vertex i to vertex ; in the proper ordes That stack is the output of the algorithm. 1. Set the value V-found equal to False, k = 1, 2,..., 2. 3. D, 0 {i} 4. while (-V. found) and (D,) Dri- for each k in D: for each edye (kl). If V. found False: V. found True V.from-k Dr+1 = Dr+1 U{t} 5. If V. found: S = EmptyStack ok=j while V.from: Push & onto S k= V. from Push konto S Push onto 3