#include

#include

using namespace std;

class Graph {

public:

Graph(int n);

~Graph();

void addEdge(int src, int tar);

void BFTraversal();

void DFTraversal();

void printVertices();

void printEdges();

private:

int vertexCount;

int edgeCount;

bool** adjMat;

void BFS(int n, bool marked[]);

void DFS(int n, bool marked[]);

};

Graph::Graph(int n=0) {

vertexCount = n;

edgeCount = 0;

if(n == 0)

adjMat = 0;

else {

adjMat = new bool* [n];

for(int i=0; i

adjMat[i] = new bool [n];

for(int i=0; i

for(int j=0; j

adjMat[i][j] = 0;

}

}

Graph::~Graph() {

for(int i=0; i

delete [] adjMat[i];

delete [] adjMat;

}

void Graph::addEdge(int src, int tar) {

if(src vertexCount-1 || tar > vertexCount-1)

cout

else if(src == tar)

cout

else if (adjMat[src][tar] == 1)

cout

else {

adjMat[src][tar] = 1;

edgeCount++;

}

}

void Graph::BFTraversal() {

// TO DO

// You are expected to call BFS() in this function,

// potentially multiple times in loops.

}

void Graph::BFS(int n, bool marked[]) {

// TO DO

// You are expected to use a queue from C++ STL.

// This function is not recursive, and you are expected to use a while loop.

}

void Graph::DFTraversal() {

// TO DO

// You are expected to call DFS() in this function,

// potentially multiple times in loops.

}

void Graph::DFS(int n, bool marked[]) {

// TO DO

// You are asked to implement this function using recursion.

// However, a for loop is expected --- the recursive calls are within the loop.

}

void Graph::printVertices() {

cout

cout

}

void Graph::printEdges() {

cout

for(int i=0; i

for(int j=0; j

if(adjMat[i][j])

cout

}

int main() {

cout

cout

int n = 0;

cin >> n;

Graph G(n);

while(1) {

cout

cout

cout

int a;

cin >> a;

cout

int b;

cin >> b;

if( a == -1 && b == -1)

break;

else

G.addEdge(a,b);

}

cout

G.printVertices();

G.printEdges();

cout

G.BFTraversal();

cout

G.DFTraversal();

return 0;

}

1. Implement the public function BFTraversal ), which outputs a breadth-first traversal of the graph. To do so, you need to implement a private function BFS (), which performs breadth-first search from a given vertex. In BFTraversal (), you may need to call BFS () multiple times (in loops) in order to perform breadth-first search in sub-graphs that are not connected NOTE: in both BFTraversal) and BFS (), whenever you can choose from multiple un visited vertices to proceed, please choose the one with the lowest index for better grading consistence. For example, you always start BFTraversal by performing BFS () or vertex 0, and then other vertices if necessary. Hint: You will need to use a queue to implement the function BFS(). You may use an int queue to store the indices to represent vertices in queue. The C++ Standard Template Library (STL) provides the template class queue for you to use by # include. See plusplus.com/reference/queue/queue/ to learn the syntax of the declaration of an int queue and its member functions Implement the public function DFTraversal (), which outputs a depth-first traversal of the graph. To do so, you need to implement a private function DFS (), which performs depth-first search from a given vertex. In DFTraversal (), you may need to call DFS () multiple times (in loops) in order to perform depth-first search in sub-graphs that are not connected. Furthermore, you are asked to implement DFS () using recursion NOTE: in both DFTraversal) and DFS (, whenever you can choose from multiple un visited vertices to proceed, please choose the one with the lowest index for better grading consistence. For example, you always start DFTraversal ) by performing DFS () on vertex 0, and then other vertices if necessary. Hint: You are expected to implement DFS () using recursion. Nonetheless, a for loop is also expected within DFS (), i.e., the recursive calls are within the loop. (This is a counterexample to disprove "a recursive function must have absolutely no loop inside".) 2