II. Part 2: Coding problem:

2.1 Description: We are asked to develop a software agent that helps a user to find his way home from a given position. He is currently in Macau and his home is in USA. To accomplish this task, you will be given a map of possible flight connections. You will be required to create a program that finds the list of countries that the agent must travel on in order to get home.

Your program must take in an arbitrarily large list of intersections and find a napossible route to take. It will then output a list of each country taken in order (see example file). An example input (described in a text file) that would contain a list of connecting countries (edges):

Macau China

Macau Hongkong

Macau Taiwan

China Japan

China India

China France

Hongkong Japan

Hongkong Korea

Taiwan India

Korea Neitherland

India Russia

France England

France USA

Japan USA

Your program would return the output of countries and other connecting locations traveled over including the starting and finishing countries, in order of travel. For example: 

Macau

China

Japan

USA

Your program also prints out the time that needed to find out the path using DepthFirstSearch (DFS), BreadthFirstSearch (BFS):

For example:

DFS 10  (milliseconds)

BFS 11     (milliseconds)

You can assume that country names will not have any white spaces in them. Additionally, the very first row has the starting state, while the very last row has the ending state just in the same way as the example. So, with other test cases, you must be able to help the agent find his way to other places as well. 

You must solve this problem using both depth first and breadth first search. Additionally, you should keep track of time requirements. Elapse time is computed by taking the difference between the time it finishes the search and the starting time. 

Your program should run as follows:

- Assume that your agent is called pathfinder.

- Run pathfinder from console.

- Given the name of the file that contains the map (say map.txt) and the name of the country where the agent departs.

- The screen output would looks like:

Path:

DFS:

// Then you display the path using DFS here

BFS:

// Then you display the path using BFS here

Time:

DFS <display the elapse time to conduct DFS here>

BFS <display the elapse time to conduct BFS here>

Data