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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx