Question

Algorithm and Data Structures

Suppose the unweighted graph graph G = (V, E), represents connections between cities in a country. Salesman wants to get from city A to city P using the unweighted graph G = (V, E) of cities.

a) Explain how the salesman use BFS algorithm to get from city A to city P passing smallest number of cities. (all steps required)

b) Now the salesman likes to visit city R on his way to city P. Describe an efficient algorithm that would determine an optimal number of cities that the salesman would pass to get from city A to city P through city R. (Consider all the possible cases) (using BFS/Dijkstra's, ALL CASES AND STEPS REQUIRED)

c) What is the total running time of each of your algorithms above? (there may be 2 different running times)

Answer 1

Let us consider the following unweighted graph

a) BFS: Step 1:   

           

Output: A P

Step 2:         

    

Output: A P Q                                     

Step 3:  

Output: A P Q R

Step 4:    

             

Output: A P Q R S                                     

Step 5:

Output: A P Q R S T                                                    

Step 6:    

Output: A P Q R S T D

The BFS of a graph starting from city A is  A P Q R S T D

The BFS Tree as follows

a) BFS algorithm to get from city A to city P passing smallest number of cities is A P

b)

BFS: Step 1:       

                 

Output: A Q   

Step 2:      

Output: A Q R                                             

Step 3:  

Output: A Q R S   

Step 4:      

Output: A Q R S D

Step 5:       

Output: A Q R S D P   

Step 6:    

Output: A Q R S D P T

BFS algorithm to get from city A to visit city R on his way to city P is A Q R S D P T

BFS Tree to get from city A to visit city R on his way to city P

c) Breadth first search:
Enqueue and Dequeue happen only once for each node. O(V)
Total time spent in scanning adjacency lists is O(E)
The total running time of BFS algorithm is O(V+E)