C++ code for the following. USE ONLY HEADERS <iostream> <queue> and <stack>: A g

Question

C++ code for the following. USE ONLY HEADERS <iostream> <queue> and <stack>:

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 0’s. 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.

Explanation / Answer

An edge of the form (x, x) is said to be a loop. If x is y’s friend several times over, that could be modeled using multiedges, multiple edges between the same pair of vertices. A graph is said to be simple if it contains no loops and multiple edges. A graph is connected if there is a path between any two vertices. A directed graph is strongly connected if there is a directed path between any two vertices.

There are two main data structures used to represent graphs. We assume the graph G = (V, E) contains n vertices and m edges. We can represent G using an n × n matrix M, where element M[i, j] is, say, 1, if (i, j) is an edge of G, and 0 if it isn’t. It may use excessive space for graphs with many vertices and relatively few edges

public class Vertex implements Comparable

{ public String name;

// label // the next four variables for search

public boolean processed;

public boolean discovered;

public Vertex predecessor;

// previous vertex public int distance;

// distance from source to it public Vertex(String v) { name = v; distance = -1; }

public int hashCode() { return name.hashCode() ;

} public String toString() { return name; }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.