Implementation of Kruskal Algorithm for Adjacency Matrix

[Eclip7e]

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).
    If the edge already exists or we try to add a loop, no edge is added.
    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).
    */
     virtual int addVertex() abstract;

    /*
    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();
};



class AdjacencyMatrixGraph: 
    public Graph
{
public:
     /*
     creates a graph with given number of vertices and no edges
     */
     AdjacencyMatrixGraph(int n=0);
     /*
     creates a copy of a given graph
     */
     AdjacencyMatrixGraph(const AdjacencyMatrixGraph&); 
     ~AdjacencyMatrixGraph();                   

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

     int addEdge(int,int,int) 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 addVertex() override; 
     int removeVertex(int) override; 
     list<int> getNeighbors(int) override; 
     int getMaxDeg() override;              
     int getMinDeg() override;  
     int getMaxDegVert() override;
     int getMinDegVert() override;

private:
    /*adjacency matrix*/


    int  **matrix;
    int n;
};

The problem is that i don't have a good idea to go about this :/

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.

[Eclip7e]

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)
                        tree.addEdge((tab+place)->v1,(tab+place)->v2,(tab+place)->weight);
                        inTree[(tab+place)->v1]=true;
                        inTree[(tab+place)->v2]=true;
                        place++;
                }

         delete [] inTree;
         delete [] tab;
         return tree;
     }