Algorithm To Use Is Below Picture 1 (78.48 KiB) Viewed 30 times
Algorithm To Use Is Below Picture 2 (91.05 KiB) Viewed 30 times
Apply Algorithm 9.3.2 Breadth-first Search to find a path from 5 to 1 in Figure 9.3.1. What would be the final value of V and D? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order, as we assumed in Example 9.3.1. Note: In Example 9.3.1, the value of 4 in the Depthset row, under k= 3, means there are 4 edges traversed to arrive at vertex 3 from vertex 2. Figure 9.3.1
Algorithm 9.3.2: Breadth-first Search — , A broadcasting algorithm for finding a path between vertex i and vertex j of a graph having n vertices. Each item Vk of a list V = {V1, V2, ...,Vn}, consists of a Boolean field Vk. found and an integer field Vk.from. The sets D1, D2, ..., called depth sets, have the property that if k e Dr, then the shortest path from vertex i to vertex k is of length r. In Step 5, a stack is used to put the vertex list for the path from the vertex i to vertex j in the proper order. That stack is the output of the algorithm. 1. Set the value Vk. found equal to False, k=1,2,...,n 2. r=0 3. Do = {i} 4. while (-V;. found) and (Dr + 0) o Dr+1 = 0 o for each k in Dr: for each edge (k,t): If V. found == False: V. found = True V. from =k Dr+1 = Dr+1 U{t} or=r +1 5. if V;. found: o S = EmptyStack o k=j o while Vk. from #i: Push k onto S k= Vk. from o Push k onto S o Push i onto S = =
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!