This is the task:

Implement theGraphMST()function inGraph.cwhich takes in a graph and returns a minimum spanning tree of the graph as a new graph. If the given graph has no minimum spanning tree, the function should return NULL. If the graph has multiple minimum spanning trees, you can return any of them.

You may use any minimum spanning tree algorithm you like. You can (and are encouraged to) make use of the priority queue ADT that we've supplied.

I'm not sure how to start and do what it says. This is Graph.c and I attached the #include .h files :

//ImplementationoftheUndirectedWeightedGraphADT

//Usesanadjacencymatrix

#include

#include

#include

#include

#include"Graph.h"

#include"PQ.h"

structgraph{

intnV;//#vertices

intnE;//#edges

double**edges;//adjacencymatrixstoringpositiveweights

//0ifnodesnotadjacent

};

staticbooldoHasCycle(Graphg,Vertexv,Vertexprev,bool*visited);

staticintvalidVertex(Graphg,Vertexv);

////////////////////////////////////////////////////////////////////////

GraphGraphNew(intnV){

assert(nV>0);

Graphg=malloc(sizeof(*g));

if(g==NULL){

fprintf(stderr,"error:outofmemory ");

exit(EXIT_FAILURE);

}

g->nV=nV;

g->nE=0;

g->edges=malloc(nV*sizeof(double*));

if(g->edges==NULL){

fprintf(stderr,"error:outofmemory ");

exit(EXIT_FAILURE);

}

for(inti=0;i

g->edges[i]=calloc(nV,sizeof(double));

if(g->edges[i]==NULL){

fprintf(stderr,"error:outofmemory ");

exit(EXIT_FAILURE);

}

}

returng;

}

voidGraphFree(Graphg){

for(inti=0;inV;i++){

free(g->edges[i]);

}

free(g->edges);

free(g);

}

////////////////////////////////////////////////////////////////////////

intGraphNumVertices(Graphg){

returng->nV;

}

boolGraphInsertEdge(Graphg,Edgee){

assert(validVertex(g,e.v));

assert(validVertex(g,e.w));

assert(e.v!=e.w);

assert(e.weight>0.0);

if(g->edges[e.v][e.w]==0.0){

g->edges[e.v][e.w]=e.weight;

g->edges[e.w][e.v]=e.weight;

g->nE++;

returntrue;

}else{

returnfalse;

}

}

boolGraphRemoveEdge(Graphg,Vertexv,Vertexw){

assert(validVertex(g,v));

assert(validVertex(g,w));

if(g->edges[v][w]!=0.0){//edgeeingraph

g->edges[v][w]=0.0;

g->edges[w][v]=0.0;

g->nE--;

returntrue;

}else{

returnfalse;

}

}

doubleGraphIsAdjacent(Graphg,Vertexv,Vertexw){

assert(validVertex(g,v));

assert(validVertex(g,w));

returng->edges[v][w];

}

voidGraphShow(Graphg){

printf("Numberofvertices:%d ",g->nV);

printf("Numberofedges:%d ",g->nE);

for(intv=0;vnV;v++){

for(intw=v+1;wnV;w++){

if(g->edges[v][w]!=0.0){

printf("Edge%d-%d:%lf ",v,w,g->edges[v][w]);

}

}

}

}

boolGraphHasCycle(Graphg){

bool*visited=calloc(g->nV,sizeof(bool));

assert(visited!=NULL);//lazyerrorchecking

for(intv=0;vnV;v++){

if(!visited[v]&&doHasCycle(g,v,v,visited)){

free(visited);

returntrue;

}

}

free(visited);

returnfalse;

}

staticbooldoHasCycle(Graphg,Vertexv,Vertexprev,bool*visited){

visited[v]=true;

for(intw=0;wnV;w++){

if(g->edges[v][w]!=0.0){

if(!visited[w]){

if(doHasCycle(g,w,v,visited)){

returntrue;

}

}elseif(w!=prev){

returntrue;

}

}

}

returnfalse;

}

GraphGraphMST(Graphg){

returng;

}

staticintvalidVertex(Graphg,Vertexv){

returnv>=0&&vnV;

}

-----------------------------------------------------------------------------------------------------------------------------------------------------------

PQ.h:

//Priorityqueueofedges

//Edgeswithsmallerweighthavehigherpriority

#ifndefPQ_H

#definePQ_H

#include

#include"Graph.h"

typedefstructPQRep*PQ;

/**

*Createsanewpriorityqueue

*Complexity:O(1)

*/

PQPQNew(void);

/**

*Freesallmemoryassociatedwiththegivenpriorityqueue

*Complexity:O(1)

*/

voidPQFree(PQpq);

/**

*Addsanedgetothepriorityqueue

*Averagecomplexity:O(logn)

*/

voidPQInsert(PQpq,Edgee);

/**

*Removesandreturnstheedgewiththesmallestweightfromthe

*priorityqueue.Ifmultipleedgeshavethesamesmallestweight,one

*ofthemwillberemoved.

*Complexity:O(logn)

*/

EdgePQExtract(PQpq);

/**

*Returnstrueifthegivenpriorityqueueisempty,orfalseotherwise

*Complexity:O(1)

*/

boolPQIsEmpty(PQpq);

/**

*Printsthegivenpriorityqueuetostdoutfordebuggingpurposes

*/

voidPQShow(PQpq);

#endif

------------------------------------------------------------------------------------------------------------------------------------------------------------------

// Interface to the Undirected Weighted Graph ADT // - Vertices are identified by integers between 0 and nV - 1, 11 where nV is the number of vertices in the graph // - Weights are doubles and must be positive // - Self-loops are not allowed #ifndef GRAPH_H #define GRAPH_H #include typedef struct graph *Graph; typedef int Vertex; // edges are pairs of vertices (end-points) typedef struct Edge { Vertex V; Vertex W; double weight; } Edge; /* * * Creates a new instance of a graph * / Graph GraphNew(int nV) ; 1* * * Frees all memory associated with the given graph * / void GraphFree (Graph g) ; /* * * Returns the number of vertices in the graph * int GraphNumVertices (Graph g) ; / * * * Inserts a edge into a graph. Does nothing if there is already an * edge between e.v' and e.w . Returns true if successful, and false * if there was already an edge. * / bool GraphInsertEdge (Graph g, Edge e); 1 * * * Removes an edge from a graph. Returns true if successful, and false * if the edge did not exist. * bool GraphRemoveEdge (Graph g, Vertex v, Vertex w); / * */** * Removes an edge from a graph. Returns true if successful, and false * if the edge did not exist. */ bool GrathemoveEdge(Graph g, Vertex v, Vertex w); /** \\ \\ \\ * Returns the weight of the edge between v and w' if it exists, or * 0.6 otherwise */ double GraphIsAdjacent(Graph g, Vertex v, Vertex w); /** * Returns true if the graph contains a cycle, and false otherwise */ bool GrathasCycle(Graph g); /** * Returns a minimum spanning tree of the given graph. The given graph * should not be modified. Returns NULL if the graph has no minimum * spanning tree. */ Graph GraphMST(Graph g); /** * Displays information about the graph */ void GraphShow(Graph g); #endif