The topology of a network is modeled with a graph. Write a C++ program that inputs a graph G by first inputting the number of vertices n followed by a sequence of pairs i j where i and j are integers between 0 and n, inclusive, representing the edges of the graph, and ending with a negative integer sentinel to indicate the end of the input. For example, 5 0 1 4 2 3 1 3 3 4-1 represents the graph G-(V,E) given by: V-{0,1,2,3,4) E 10,13,11,43,{2,3),11,3),{3,4)) Your program will compute the diameter of G in the case when G is connected and the connected components of G, otherwise You can proceed as follows: Implement the graph G with its adjacency matrix Implement the function BFS (G, v) for performing a breadth-first search where the visit operation involves computing the distance from v to the vertex being visited. This will require a queue, which you can get from the Standard Template Library (STL) Implement a function Diameter (G)that returns the diameter of G ifG is connected and -1, otherwise Implement a function Components (G) for computing the vertex sets of the connected components of G. Components () will employ a BFT (Breadth-First Traversal), which involves calling BFS (G,v),v-0,1,.. n -1, as discussed in class * Store the entire source code for your program in a single file. Your program should run using Visual C++ Have your program output the adjacency matrix of the graph as well as the diameter in the case when G is connected and the connected components, otherwise. Output the connected components by outputting the vertex set of each connected component. Run your program for each of the two cases, G connected and G disconnected, for a graph of your choosing and attach a hard copy of this output after your source code Your program should be user-friendly, well-commented, with the output well- documented The topology of a network is modeled with a graph. Write a C++ program that inputs a graph G by first inputting the number of vertices n followed by a sequence of pairs i j where i and j are integers between 0 and n, inclusive, representing the edges of the graph, and ending with a negative integer sentinel to indicate the end of the input. For example, 5 0 1 4 2 3 1 3 3 4-1 represents the graph G-(V,E) given by: V-{0,1,2,3,4) E 10,13,11,43,{2,3),11,3),{3,4)) Your program will compute the diameter of G in the case when G is connected and the connected components of G, otherwise You can proceed as follows: Implement the graph G with its adjacency matrix Implement the function BFS (G, v) for performing a breadth-first search where the visit operation involves computing the distance from v to the vertex being visited. This will require a queue, which you can get from the Standard Template Library (STL) Implement a function Diameter (G)that returns the diameter of G ifG is connected and -1, otherwise Implement a function Components (G) for computing the vertex sets of the connected components of G. Components () will employ a BFT (Breadth-First Traversal), which involves calling BFS (G,v),v-0,1,.. n -1, as discussed in class * Store the entire source code for your program in a single file. Your program should run using Visual C++ Have your program output the adjacency matrix of the graph as well as the diameter in the case when G is connected and the connected components, otherwise. Output the connected components by outputting the vertex set of each connected component. Run your program for each of the two cases, G connected and G disconnected, for a graph of your choosing and attach a hard copy of this output after your source code Your program should be user-friendly, well-commented, with the output well- documented
