Answer Happy

implement a c++ program to count Number of connected componentsin an undirected graph using the following structure. For this taskyou can use (DFS, Prim, Kurskel, Dijkstra) should also beimplemented.
#include <iostream>#include <cstdlib>#include <time.h> // Used by timing functions#include <ctime>
using std::cout;using std::cin;using std::endl;using std::string;using std::ostream;
#define UNVISITED 0#define VISITED 1#define ROOT -1#define INFINITY 9999
class Graph {private: void operator =(const Graph&) {} //Protect assignment Graph(const Graph&) {} //Protect copy constructor
public: Graph() {} // Defaultconstructor virtual ~Graph() {} // Base destructor
// Initialize a graph of n vertices virtual void Init(int n) =0;
// Return: the number of vertices and edges virtual int n() =0; virtual int e() =0;
// Return v's first neighbor virtual int first(int v) =0;
// Return v's next neighbor virtual int next(int v, int w) =0;
// Set the weight for an edge // i, j: The vertices // wgt: Edge weight virtual void setEdge(int v1, int v2, int wght) =0;
// Delete an edge // i, j: The vertices virtual void delEdge(int v1, int v2) =0;
// Determine if an edge is in the graph // i, j: The vertices // Return: true if edge i,j has non-zero weight
class Graphl : public Graph {private: List<Edge>** vertex; //List headers int numVertex, numEdge; // Number of vertices,edges int *mark; // Pointer to mark arraypublic: Graphl(int numVert) { Init(numVert); }
~Graphl() { // Destructor delete [] mark; // Return dynamically allocatedmemory for (int i=0; i<numVertex; i++) delete []vertex; delete [] vertex; }
void Init(int n) { int i; numVertex = n; numEdge = 0; mark = new int[n]; // Initialize markarray for (i=0; i<numVertex; i++) mark =UNVISITED; // Create and initialize adjacency lists vertex = (List<Edge>**) newList<Edge>*[numVertex]; for (i=0; i<numVertex; i++) vertex = new LList<Edge>(); }
int n() { return numVertex; } // Number of vertices int e() { return numEdge; } // Number of edges
int first(int v) { // Return first neighbor of "v" if (vertex[v]->length() == 0) return numVertex; // Noneighbor vertex[v]->moveToStart(); Edge it = vertex[v]->getValue(); return it.vertex(); }
// Get v's next neighbor after w int next(int v, int w) { Edge it; if (isEdge(v, w)) { if ((vertex[v]->currPos()+1) <vertex[v]->length()) { vertex[v]->next(); it = vertex[v]->getValue(); return it.vertex(); } } return n(); // No neighbor } // Set edge (i, j) to "weight" void setEdge(int i, int j, int weight) { Assert(weight>0, "May not set weight to 0"); Edge currEdge(j, weight); if (isEdge(i, j)) { // Edge already exists ingraph vertex->remove(); vertex->insert(currEdge); } else { // Keep neighbors sorted by vertex index numEdge++; for (vertex->moveToStart(); vertex->currPos()< vertex->length(); vertex->next()){ Edge temp =vertex->getValue(); if (temp.vertex() > j) break; } vertex[i]->insert(currEdge); } }
virtual bool isEdge(int i, int j) =0;
// Return an edge's weight // i, j: The vertices // Return: The weight of edge i,j, or zero virtual int weight(int v1, int v2) =0;
// Get and Set the mark value for a vertex // v: The vertex // val: The value to set virtual int getMark(int v) =0; virtual void setMark(int v, int val) =0;};
int main(){
return 0;}