C++ code for the following:

A graph G = (V, E) consists of vertex set V and the edge set E. Assume the graph G is undirected implying that the edges have no direction,and that the graph is connected (there exists a path between every pair of nodes).

In the above we have provided a graph and an edge list representation of the graph. The above graph can be stored in a matrix which is declared as follows. This matrix is called the adjacency matrix.

bool AdjacencyMatrix[7][7];

The matrix element AdjacencyMatrix[i][j] is set to true if there is an edge between nodes numbered i and j. For example, for the graph above AdjacencyMatrix[4][3] is set to true, since there is an edge between nodes 4 and 3. Since the edges no direction (undirected graph), the matrix element corresponding to edge (3,4) AdjacencyMatrix[3][4] is also set to true. We will assume that AdjacencyMatrix[i][i] for all i, is set to false.

We will now show the entire adjacency matrix for the above graph in the following (note that a 0 represents false and 1 represents true).

7 Number of nodes

2 4 Edge from 2 to 4

0 1

3 0

3 6

6 4

3 4

1 3

1 2

2 4

5 2

4 5

In C/C++ programming language each bool takes 8 bits. The total size consumed by the matrix is 7*7*8 bits = 49 Bytes.

Bit Representation of Adjacency Matrix

We can represent each row of the above matrix by an unsigned char (8 bits). Note that we need only seven bits, but we can assume that the last bit as a zero. For example, the bit 8 bits corresponding to the first row will be 01010000 which corresponds to the letter P. The second rows bits are 10110000 and it corresponds to the character (degree symbol). Note that in this case, the first bit is actually the most significant bit, and the least significant bit is the unused 8th bit (in other words, all of your values will be even numbers). In this representation, the total number of bits will 8*8 bits = 8 bytes.

Now, let us say that we have 10 nodes in a graph. The size of AdjacencyMatrix structure using the bool data type will be 10*10*8 = 100 bytes. For the bit representation of the matrix, we need two unsigned character per row. The 6 lower order bits of the second unsigned character will be all 0s. The will give us a total size of 10*2 bytes (one byte for each unsigned character).

1. Create Graph Class with Bit Representation of Adjacency Matrix

2. Add Edge

3. Using Queue Standard Template Library for use as part of BFS (see below)

4. Ostream operator to print the graph in the edge list format

5. Implement the copy constructor and the overloaded = (assignment) operator

6. Breadth First Search (BFS) and output the parent array representation of the BFS tree. This function will take as input the Graph object and the start vertex p.

7. Perform Depth First Search (DFS) and output the parent array representation of the DFS tree. This function will take as input the Graph object and the start vertex p.

8. Document code thoroughly.

6 3