Programming Project

Connected Components of a Network

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 1, 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 1 4 2 3 1 3 3 4 -1

represents the graph G =(V,E ) given by:

V ={0,1,2,3,4}

E ={{0,1},{1,4},{2,3},{1,3},{3,4}}.

Your program will compute the (connected) components of G

You can proceed as follows:

Implement the graph G with using pointer-based adjacency lists (using an array of header nodes and a linked list for each header node). Your class Graph should include constructors and a destructor, operations of edge addition, edge deletion, etc.

Implement the function DFS(G,v) for performing a depth-first search.

Implement a function Components(G)for computing the vertex sets of the connected components of G. Components()will employ a DFT (Depth-First Traversal), which involves calling DFS(G,v), v =0,1, .. n 1.

For purposes of grading, store the entire source code, including the graph class and its implementation, in a single .cpp file. Your program should run using Visual C++.

Have your program output the adjacency matrix of the graph as well as the connected components. Output the components by outputting the vertex set of each component. Run your program for a disconnected graph (i.e., having at least two components) of your choosing and submit this output in additional to your source code.

Your program should be user-friendly, well-commented, with the output well-documented.