Construct an undirected graph to represent non-stop airline flights between cities in the world. It should contain at least one pair of cities, between which there is no non-stop flight, but there is a route (or path) between them. Implement the Breadth-first search (BFS) algorithm (using Java or C/C++) to find a route between two cities with the minimum number of stops. That is, when user inputs the names of two cities, your program should return one route with the smallest possible number of stop(s). If a non-stop flight is available, it will just return the departure city and arrival city.
In your report and presentation, please include a description and results of the following steps:
Measure the CPU times of your program on graphs of different sizes, and analyse how the running times depend on the numbers of cities and non-stop flights. Explain whether Depth-first search (DFS) algorithm can be used in place of BFS, why or why not.
Includes:
- source code
- text file
note: if using eclipse, change the text output encoding to get a prettier printout :-) file -> properties -> text file encoding: UTF-8