Find a way to print the path from one vertex to another from the given program below :

#include #include #include using namespace std;

class Graph { private: int numVertices; int maxVertices; string *vertices; int **edges; bool *visited;

public: Graph() { numVertices = 0; maxVertices = 50; vertices = new string[50]; edges = new int*[50]; for(int i=0; i<50; i++) { edges[i] = new int[50]; } visited = new bool[50]; }

Graph(int maxV) { numVertices = 0; maxVertices = maxV; vertices = new string[maxV]; edges = new int*[maxV]; for(int i=0; i

void makeEmpty() { numVertices = 0; }

bool isEmpty() { if(numVertices = 0) { return true; } else { return false; } }

bool isFull() { if(numVertices = maxVertices) { return true; } else { return false; } }

void addVertex(string vertex) { vertices[numVertices] = vertex; for (int index = 0; index < numVertices; index++) { edges[numVertices][index] = 0; edges[index][numVertices] = 0; } numVertices++; }

void addEdge(string fromVertex, string toVertex, int weight) { int row = indexIs(vertices, fromVertex); int col = indexIs(vertices, toVertex); edges[row][col] = weight; }

int weightIs(string fromVertex, string toVertex) { int row = indexIs(vertices, fromVertex); int col = indexIs(vertices, toVertex); return edges[row][col]; }

int indexIs(string *vertices, string vertex) { for(int i=0; i

void getAdjacentVertices(string vertex, queue &adjVertices) { int fromIndex; int toIndex; fromIndex = indexIs(vertices, vertex); for (toIndex = 0; toIndex < numVertices; toIndex++) { if (edges[fromIndex][toIndex] != 0) { adjVertices.push(vertices[toIndex]); // in C++ STL Queue, push = enqueue // and pop = dequeue } } }

void clearVisited() { for(int i=0; i

void markVertex(string vertex) { visited[indexIs(vertices,vertex)] = true; }

bool isMarked(string vertex) { return visited[indexIs(vertices,vertex)]; }

void printGraph() { for(int i=0; i

void depthFirstSearch(Graph graph, string startVertex, string endVertex) { stack vStack; queue adjacentVertices; bool found = false; string vertex; string item; graph.clearVisited(); vStack.push(startVertex); cout << "Visited nodes: "; do { vertex = vStack.top(); vStack.pop(); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.isMarked(vertex)) { graph.markVertex(vertex); cout << vertex << " "; graph.getAdjacentVertices(vertex, adjacentVertices); while (!adjacentVertices.empty()) { item = adjacentVertices.front(); adjacentVertices.pop(); if (!graph.isMarked(item)) vStack.push(item); } } } } while (!vStack.empty() && !found);

if (!found) cout << " Path not found." << endl; }

void breadthFirstSearch(Graph graph, string startVertex, string endVertex) { queue mainQueue; queue adjacentVertices; bool found = false; string vertex; string item; graph.clearVisited(); mainQueue.push(startVertex); cout << "Visited nodes: "; do { vertex = mainQueue.front(); mainQueue.pop(); if (vertex == endVertex) { cout << vertex; found = true; } else { if (!graph.isMarked(vertex)) { graph.markVertex(vertex); cout << vertex << " "; graph.getAdjacentVertices(vertex, adjacentVertices); while (!adjacentVertices.empty()) { item = adjacentVertices.front(); adjacentVertices.pop(); if (!graph.isMarked(item)) mainQueue.push(item); } } } } while (!mainQueue.empty() && !found);

if (!found) cout << " Path not found." << endl; }

int main() { Graph g(8);

g.addVertex("A"); g.addVertex("B"); g.addVertex("C"); g.addVertex("D"); g.addVertex("E"); g.addVertex("F"); g.addVertex("G"); g.addVertex("H");

g.addEdge("A","B",1); g.addEdge("D","C",1); g.addEdge("D","E",1); g.addEdge("D","F",1); g.addEdge("E","G",1); g.addEdge("F","C",1); g.addEdge("G","D",1); g.addEdge("G","H",1); g.addEdge("H","A",1); g.addEdge("H","B",1);

g.printGraph(); depthFirstSearch(g,"D","B"); cout << endl; breadthFirstSearch(g,"D","B"); }