our programs will be written in C++. I will be using the following compiler and libraries to compile and run your programs:

• TDM-GCC-64.7z
• CSC1310.7z //place the CSC1310 and random folders as subdirectories of your working directory
• build.bat
• Makefile

Program #1 Graphs 15% Due: 02/25/2019 Assignment:

In this assignment, you will be implementing a Graph using both an adjacency matrix and an adjacency list. You will use the adjacency matrix to perform a depth first search and the adjacency list to perform a breadth first search. Make sure to account for all connected components. Assume that any objects (the T parameter) placed in the Graph will have a String* getKey() method. Use the Tokens class to read in the edge information from the text file.

The required public Graph operations are as follows:

• Graph(int max_num_vertices) //constructor should accept the maximum number of vertices allowed in the graph
• virtual ~Graph()
• void addVertex(T* item) //allow items (items are identified by String search keys) to be stored in the Graph vertices
• void addEdge(String* start_vertex_key, String* end_vertex_key, double edge_weight) //add a directed edge between two vertices
• ListLinked* dfs() //perform a depth first search, adding items to a linked list
• ListLinked* bfs() //perform a breadth first search, adding items to a linked list

The vertices of the Graph will be read in from a text file as in the following file:

• romanian_cities.txt
• vertices.txt

The edges of the Graph will be read in from a text file as in the following file:

• romanian_mileages.txt
• edges.txt

The program will run by specifying the vertices and edges text files as command line arguments. See the sample output below (the order in which the vertices and edges were added determines the output order, depending on search method):

BFS Craiova Pitesti Dobreta Rimnicu Uilcea Bucharest Mehadia Sibiu Fagaras Giurgiu Urziceni Lugoj radea Arad Hirsoua Uaslui Timisoara Zerind Eforie Iasi Nearnt DFS Craiova Pitesti Bucharest Fagaras Sibiu Arad Zerind radea Timisoara Lugoj Mehadia Dobreta Rimnicu Uilcea Giurgiu Urziceni Hirsoua Eforie Uaslui Iasi Nearnt B04238679115 D02679-83415 B04238679115 D02679-83415