0

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.