Hello everyone,

I want to implement Kruskal algorithm for finding minimum spanning tree in Adjacency Matrix for my program.

So I want to write method Graph& getMinSpanningTree() .

I have 2 classes:

``````class Graph
{
public:
/*
Adds an edge between given vertices. Third argument is a weight of an edge (1 by default).
Returns:
0 if an edge is added
-1 if we try to create a loop
-2 if there are no such vertices
-3 if the edge already exists
*/
virtual int addEdge(int u,int v,int weight=1) abstract;

/*
Removes an edge between given vertices.
If the edge does not exist, nothing is changed.
Returns:
0 if an edge is removed
-1 if an edge does not exist
-2 if vertices do not exist
*/
virtual int removeEdge(int, int) abstract;

/*
Returns:
1 if given vertices are connected by an egde
0 if the vertices are not connected
-1 if the vertices do not exist
*/
virtual int areConnected(int,int) abstract;

/*
Returns:
the weight of an edge between given vertices.
If the vertices or an edge do not exists, return value is not specified.
*/
virtual int getWeight(int,int) abstract;

/*
Prints the representation of a graph.
*/
virtual void show() abstract;

/*
Returns the number of vertices in a graph.
*/
virtual int getVerticesCount() abstract;

/*
Returns the number of edges in a graph.
*/
virtual int getEdgesCount() abstract;

/*
Returns:
degree of the given vertex
-1 if no such vertex exists.
*/
virtual int getDegree(int) abstract;

/* Return a reference to the clone of the graph (with the same representation) */
virtual Graph& clone() abstract;

/* Return a reference to the empty graph with n vertices and the same representation */
virtual Graph& empty(int) abstract;

/*
Adds new isolated vertex to a graph.
Returns:
0 if everything is OK
-1 in case of error (e.g. with memory allocation).
*/

/*
Removes given vertex from the graph and all the edges containing it.
The remaining vertices change their numbers - e.g. if we delete vertex 3, the vertex 4 becomes vertex 3, vertex 7 becomes vertex 6 and so on.
Returns:
0 if no error occurs
-1 otherwise
*/
virtual int removeVertex(int) abstract;

/*
Returns:
a list of neighbors of a given vertex (for isolated vertex this list is empty)
If no such vertex exists, then the return value is not specified.
*/
virtual list<int> getNeighbors(int) abstract;

/*
Returns the maximum (minimum) degree in a graph.
If the graph is empty, returned value is not specified.
*/
virtual int getMaxDeg() abstract;
virtual int getMinDeg() abstract;

/*
Returns the number of the vertex with maximum (minimum) degree in a graph.
If the graph is empty, returned value is not specified.
*/
virtual int getMaxDegVert() abstract;
virtual int getMinDegVert() abstract;

/*
Returns a spanning tree of a given graph
*/
Graph& getMinSpanningTree();
};

public Graph
{
public:
/*
creates a graph with given number of vertices and no edges
*/
/*
creates a copy of a given graph
*/

void show() override;
int getVerticesCount() override;

int removeEdge(int, int) override;
int getEdgesCount() override;
int getDegree(int) override;
int areConnected(int,int) override;
int getWeight(int,int) override;

Graph& clone() override;
Graph& empty(int) override;

///////////////////////////
int removeVertex(int) override;
list<int> getNeighbors(int) override;
int getMaxDeg() override;
int getMinDeg() override;
int getMaxDegVert() override;
int getMinDegVert() override;

private:

int  **matrix;
int n;
};
``````

Maybe I should first create method for sorting edges depending on their weight and this method will save information about:weight and which vertices edge connects. ?

If you could explain me what is the best way to go about it I would appreciate.

Ok I think i created kruskal algorithm, but not entirely correct because it creates trees and doesn't join them at the end :/ .

Here's the code any idea what should be added?

``````Graph& Graph::getMinSpanningTree()
{
int n = this->getVerticesCount();
bool* inTree = new bool[n];
Graph& tree = this->empty(n);

int v = this->getEdgesCount();
cords* tab = new cords[v];

int place=0;
for(int i=1;i<n;i++)
for(int j = 0;j < i;j++)
{
if(this->getWeight(i,j)>0)
{
(tab+place)->weight=this->getWeight(i,j);
(tab+place)->v1=i;
(tab+place)->v2=j;
place++;
}
}
place=0;

for(int i =0;i<v;i++)
cout<<tab[i].weight<<",";

for(int y=0; y < v; y++)
for ( int k =0; k < v - 1 - y; k++ )
{
if((tab+k)->weight > (tab+k+1)->weight)
{
cords temp = tab[k+1];
tab[k+1] = tab[k];
tab[k] = temp;
}
}
cout<<endl;
for(int i =0;i<v;i++)
cout<<tab[i].weight<<".";

for (int i=0; i<n; i++)
inTree[i]=false;

for(int i=0;i<v;i++)
{
if(inTree[(tab+place)->v1]==false || inTree[(tab+place)->v2]==false)