In C++ only, make a menu-driven program with the following functions working correctly. Implement the following graph do not use any built-in functions.

Class Graph(){
1. Graph()
2. addNode (string) // to inset new vertex in the graph.
3. addEdge (string, string, int) to insert a new vertex in the graph.
4. checked (string, string)// to check whether an edge exists between two vertices.
5. adjacencyMatrix() // graph representation using AM.
6. adjacencyList() // graph representation using AL.
7. check degree(string) // to check the degree of a specified vertex.
8. check neighbors(string) // to check the neighbors of the specified vertex.
9. checkPath (string, string) // to find the path between two specified vertices, if there’s no
direct edge between the nodes, follow the neighbors. Always choose the edge with minimum
cost in case there are many edges at intermediatory vertices between source and destination
vertex.
10. graphTraversal (string) // to traverse the graph using BFS or DFS traversal methods.

11. graphTree () // converts the graph into acyclic tree.
12. ~Graph()

 

732 Florida 516 -1314- Alabama 1821 378 Georgia -1153- Denver 2625 -1238- Washington -652- 2402 3704 -1304- New york -268- California 3928 3595 543- Columbia 3478 -3471- 437 Virginia -992- 22 South Carolina 459