Assignment 6 Direct flights

Programming Assignment 6 The Final Challange
Abstract
In this assignment we create a graph to represent the direct flights between different departure cities. By
combining our previously studied Data Structures, we are able to find any path between any two cities in
the least amount of flight connections necessary. The Data Structures we will use are the Graph, Dequeue,
Adjacency List, Lists, Queues, Stacks and Unordered Sets ADTs. This is the final project for CSCE 221
Spring 2017.
Problem 1
A) Describe your Data Structure used in your project
In this program we used the following Data Structures for the implementation: the Graph Data Structure
which organized and builds the map between Verticies and their respective connections between them. The
class contains a vector called adj list which contains a list of Edge List objects which are the connections to
that between adjacent vertices. The Graph Data Strucutre also contains a vector of Vertex objects which
store the individual vertex objects from our input data. Another Data Strucutre that I implemented in this
class is the Unordered Set which is used for partitioning the groups for part two, when finding if the input
cities can be partitioned into two disjoined sets.
This Graph Class functions will build the graph, display the graph and find the shortest path from a vertex
A to a vertex B.
B) Describe the Algorithms used in your Project
The Bredth-First Search Algorithm (BFS) is used in find the shortest path from a vertex A to a vertex B in
our graph. The algorithm works by implementing a Queue Data Structure that will store the initial starting
vertex. It will tests and add each adjacent vertex untill the desired end destination. If the vertex is not
found after visiting the first connecting flights, it will continue onto each new vertex that was enqueued in
the queue and repeat the test to check the new connections. Once the desired end vertex is found, it will
display the output from the shortest path from the start vertex to the end vertex. This is done by recording
a parent node member function for each adjacent vertex that we visit. Ultimately, this shortestPath(int
A,int B) will find the shortest path from a starting Vertex A, to an ending Vertex B in our graph.
C) Evidence
I tested the input data 1, 2, and 3 to check whether the connecting flights could be partitioned into a disjoined
set. The input data 1 and 3 were successfully partitioned since each adjacent vertex could be separated into
two individual sets. Input data 2 failed because city number 2 was placed into both sets, and failed out test
for a disjoined set.
Below are some screenshots of the testing of my code.
Page 2 of 3
Robert Quan CSCE 221 (Dr. Leyk ): Programming Assignment 6 The Final Challange Problem 1
Figure 1: Testing the code for correctness, input1
Figure 2: Testing the code for correctness, input3
Figure 3: Testing the code for correctness, input3
Page 3 of 3