This will be coded in Java. The text files with vertices just have the vertices being seperated by a new line, while the edges text files have 3 strings per line seperated by a space which contain the start vertext, end vertex, and the weight of that edge.

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.

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

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

List dfs() //perform a depth first search, adding items to a linked list

List 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

top_sort_vertices.txt

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

romanian_mileages.txt

top_sort_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 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