Can someone please help me in c++ ?

Enter a string through the keyboard For end press Ctrl+A Enter an integer number through the keyboard Create a directed graph whose vertices will have the values of the characters of the string, and the edges will be randomly generated, with the highest value of any edge being the value entered through the keyboard Create a function that will return a minimum spanning tree for the given graph according the Dijkstras algorithm, which will have the greatest total weight of all possible minimum spanning trees of that graph In other words, calculate the sum of the edges of the minimum spanning trees starting from each vertex in the graph and choose what MST (and its initial vertex) which has the largest total weight of its edges

Dijkstras algorithm:

#include using namespace std; #include "GRAPH.h" #include "queue.h" #include "node1.h"

// Returns a minimum spanning tree (in a form of a graph) according Kruskal's algorithm template GRAPH Dijkstra(GRAPH g, T veStart) { // creating the vertices from the input graph int numberVertices = g.numberVertices(); T *vertex = new T[numberVertices]; g.allVertices(vertex, numberVertices);

int i, j; bool directed; int max; int queuesize; int queueoffsize; bool traversed;

// creating a copy of the graph GRAPH copy = g.copy(); // unit graph GRAPH unit(vertex, numberVertices);

// vertices From and To between which we'll calculate the edge weight T veFrom, veTo, veFromCurrent, veToCurrent;

// queue in which vertices will be temporary stored, due to the "growing" of the tree QUEUE queue; // queue that will contain all the vertices that are not part of the tree, while "growing" QUEUE queueOff; for(i = 0; i < numberVertices; i++) queueOff.enqueue(vertex[i]);

directed = copy.isDirected();

// finding the maximum edge in the tree copy.maxEdge(veFrom, veTo); max = copy.weightEdge(veFrom, veTo);

// we begin with the starting vertex queuesize = queue.size();

veFrom = veStart;

//we enqueue the first vertex queue.enqueue(veFrom); //and dequeue it from the queueOff while(queueOff.peek() != veFrom) queueOff.enqueue(queueOff.dequeue()); queueOff.dequeue();

traversed = false;

while(!traversed) { if((queuesize = queue.size()) == copy.numberVertices()) break;

int min = max; int weightCurrent;

for(i = 0; i < queuesize; i++) { veFromCurrent = queue.dequeue(); copy.minEdgeFrom(veFromCurrent, veToCurrent);

if(veToCurrent == (T)NULL) { queue.enqueue(veFromCurrent); traversed = true; break; }

weightCurrent = copy.weightEdge(veFromCurrent, veToCurrent); if((weightCurrent <= min) && (weightCurrent > 0)) { if(!unit.edgeFromTo(veStart, veToCurrent) && (veToCurrent != veStart)) // if there isn't a cycle, it is updated { min = weightCurrent; veFrom = veFromCurrent; veTo = veToCurrent; } else // if there is a cycle, it breaks { traversed = true; queue.enqueue(veFromCurrent); break; } } queue.enqueue(veFromCurrent); }

if(!traversed) { unit.setEdge(veFrom, veTo, 1, directed); copy.deleteEdge(veFrom, veTo); queue.enqueue(veTo); while(queueOff.peek() != veTo) queueOff.enqueue(queueOff.dequeue()); queueOff.dequeue(); } else { if(queue.size() == copy.numberVertices()) //if there isn't a vertex to go to, continue; //we go to the next cycle, //which represents the end else if(veToCurrent == (T)NULL) { copy.deleteVertex(veFromCurrent); while(queue.peek() != veFromCurrent) queue.enqueue(queue.dequeue()); queue.dequeue(); } else copy.deleteEdge(veFromCurrent, veToCurrent, directed);

// checks if there is an edge from the root (start) of the tree to each vertex off the tree queueoffsize = queueOff.size(); queuesize = queue.size(); for(i = 0; i < queuesize; i++) { for(j = 0; j < queueoffsize; j++) { if(copy.edgeFromTo(queue.peek(), queueOff.peek())) // if yes, not all is traversed { traversed = false; break; } queueOff.enqueue(queueOff.dequeue()); }

if(!traversed) break;

queue.enqueue(queue.dequeue()); } } }

// creating the final tree from the unit graph copy = g.copy();

for(i = 0; i < numberVertices; i++) for(j = 0; j < numberVertices; j++) { if(unit.existEdge(vertex[i], vertex[j])) copy.setEdge(vertex[i], vertex[j], g.weightEdge(vertex[i], vertex[j]), directed); else if(copy.existEdge(vertex[i], vertex[j])) copy.deleteEdge(vertex[i], vertex[j], directed); }

return copy; }

void main() { char vertex[] = {'S', 'R', 'G', 'B', 'O', 'T', 'V'}; int numberVertices = sizeof(vertex)/sizeof(char); GRAPH g(vertex, numberVertices);

/* g.setEdge('S', 'T', 30, true); g.setEdge('R', 'B', 150, true); g.setEdge('B', 'O', 60, true); g.setEdge('G', 'T', 20, true); g.setEdge('O', 'T', 100, true); g.setEdge('B', 'S', 120, true); g.setEdge('G', 'R', 200, true); g.setEdge('S', 'V', 50, true); g.setEdge('V', 'R', 130, true); */

g.setEdge('S', 'R', 10, true); // g.setEdge('B', 'S', 80, true); g.setEdge('S', 'T', 120, true); g.setEdge('G', 'R', 40, true); g.setEdge('R', 'O', 60, true); g.setEdge('R', 'V', 120, true); g.setEdge('R', 'T', 90, true); g.setEdge('O', 'G', 100, true); g.setEdge('G', 'B', 30, true); g.setEdge('O', 'B', 80, true); g.setEdge('T', 'O', 20, true); g.setEdge('V', 'T', 30, true);

// g.makeRandom(vertex, 7, 12, true);

cout << " The graph g:" << endl; g.print();

char veStart = 'S'; GRAPH tree = Dijkstra(g, veStart);

cout << " The minimal spanning tree according Dijkstra's algorithm, starting at " << veStart << ": " << endl; tree.print(); }