2. Apply Algorithm 9.3.8 to find a path from d to c in the road graph...

Transcribed Image Text:

2. Apply Algorithm 9.3.8 to find a path from d to c in the road graph in Example 9.1.10 using the edge list in that example. Assume that the elements of the depth sets are put into ascending order. Example 9.1.10. An Undirected Graph. A network of computers can be described easily using a graph. Figure 9.1.11 describes a network of five computers, a, b, c, d, and e. An edge between any two vertices indicates that direct two-way communication is possible between the two computers. Note that the edges of this graph are not directed. This is due to the fact that the relation that is being displayed is symmetric (i.e., if X can communicate with Y, then Y can communicate with X). Although directed edges could be used here, it would simply clutter the graph. a d Figure 9.1.11. Communications Map Figure 9.1.12. Island Road Map Algorithm 9.3.8. 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 V. from. The sets D1, D2,..., called depth sets, have the property that if k 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 ) Dr+1 = 0 for each k in Dr: for each edge (k,t): If Vt. found == False: Vt. found True Vt. from = k - Dr+1 = Dr+1 U {t} r = r +1 5. if V;. found: S = EmptyStack k = j while V. from i: Pushk onto S k = Vk. from Push k onto S Push i onto S in-context 2. Apply Algorithm 9.3.8 to find a path from d to c in the road graph in Example 9.1.10 using the edge list in that example. Assume that the elements of the depth sets are put into ascending order. Example 9.1.10. An Undirected Graph. A network of computers can be described easily using a graph. Figure 9.1.11 describes a network of five computers, a, b, c, d, and e. An edge between any two vertices indicates that direct two-way communication is possible between the two computers. Note that the edges of this graph are not directed. This is due to the fact that the relation that is being displayed is symmetric (i.e., if X can communicate with Y, then Y can communicate with X). Although directed edges could be used here, it would simply clutter the graph. a d Figure 9.1.11. Communications Map Figure 9.1.12. Island Road Map Algorithm 9.3.8. 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 V. from. The sets D1, D2,..., called depth sets, have the property that if k 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 ) Dr+1 = 0 for each k in Dr: for each edge (k,t): If Vt. found == False: Vt. found True Vt. from = k - Dr+1 = Dr+1 U {t} r = r +1 5. if V;. found: S = EmptyStack k = j while V. from i: Pushk onto S k = Vk. from Push k onto S Push i onto S in-context