这个作业是根据地铁地图完成相应的数据结构和算法

COIS 3020H: Data Structures and Algorithms II

Below is the iconic subway map of London (England). Although the map has evolved over the years, its

fundamental and revolutionary design by Harry Beck has remained largely unchanged since it was first

introduced to the British public in 1933. In graph theoretic terms, each subway station is a vertex, and each

edge between a pair of stations is a subway connection. Each connection is coloured to represent its part of a

subway line, and more than one connection may run between adjacent stations. For example, yellow and green

connections run between Westminster and St. James’s Park.

The subway map of London or any other subway system may be represented as a variation of the adjacency list

implementation as shown below

Task 1: Implement each of the methods above, keeping in the mind the following requirements.

1. Each subway connection (edge) is undirected.

2. Each subway connection is coloured as part of a subway line.

3. An adjacent pair of subway stations may have multiple subway connections differentiated by colour.

4. Each subway station (vertex) stores its connections (edges) to adjacent stations in a linked list.

Task 2: Using a breadth-first search, implement a method called FastestRoute (from, to) which outputs the

shortest sequence of subway stops (including transfers) between two given stations. (16%)

Task 3: Using a depth-first search, implement a method called CriticalConnections ( ) which outputs each

connection (edge) which breaks the subway map into two parts if it is removed. (16%)

Task 4: Implement a main program to create your own subway map and to drive your test cases. (10%)

Task 5: Draw your own connected subway map and prepare your test cases. Include the map, test cases, and

test results in a separate .pdf test document.