Problem 1
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.
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.
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 code.
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
