Here are some basic definitions we will need for the following discussion.
Kruskal's algorithm is a procedure for constructing a minimum spanning tree from a collection of edges. In the following, we will represent each edge in the form (u , v), where u and v are the keys of the vertices the edge connects.
Here are the steps in Kruskal's algorithm for a graph with |E | edges and |V | vertices.
The main technical problem in implementing Kruskal's algorithm is detecting cycles. Here is one possible approach to the cycle problem.
We are going to form sets of vertices. (In practice, these will be sets of pointers to vertices, but for the discussion here I will pretend that the sets are sets of vertices.) Initially, before we have added any edges to the spanning tree, all vertices in the graph will be placed in distinct sets. Each time we consider an edge (u , v), we check to see if the vertices u and v that the edge connects are in distinct sets. If they are, accept the edge for use in the spanning tree and merge the sets that u and v belong to to represent the fact that this new edge has joined what were formerly disjoint sets of vertices together. If an edge (u , v) joins vertices that are already in the same set, we will discard the edge, because that edge would form a cycle with already added edges if we were to add it.
How do we determine whether or not two vertices are in the same set? We equip each vertex with an extra pointer called a representative pointer. That pointer points to another vertex in the same set as the given vertex. Every set will have one special element called the representative of that set. The representative of a given set will be the only member of that set whose representative pointer points to itself. Thus, when presented with any given vertex, we can jump over a chain of representative links until we come to the representative of the set that the original vertex belongs to. Two vertices belong to the same set if they have the same set representative. We can tell that two vertices belong to distinct sets by verifying that their set representatives are not the same.
To form the union of two sets in this scheme, we make the representative of the first set point to the representative of the second set. By doing this, we make the representative of the second set become the new representative for all of the elements in the first set. This effectively merges the two sets into one.
To implement this scheme, we introduce the following class:
class SetElement
{
private:
SetElement* repPtr;
public:
SetElement() { repPtr = this; }
SetElement* getRepresentative() {
SetElement* representative = repPtr;
while(representative->repPtr != representative)
representative = representative->repPtr;
return representative;
}
void unionWith(SetElement* other) {
SetElement* myRep = getRepresentative();
SetElement* otherRep = other->getRepresentative();
if(myRep != otherRep)
myRep->repPtr = otherRep;
}
};
This class implements the necessary algorithms for finding set representatives and forming the union of two sets.
In our implementation of Kruskal's algorithm, we will make our vertex class be a subclass of the SetElement class so that vertices can use the scheme described above to detect cycles.
Here is the outline of some classes needed to represent a graph with undirected, weighted edges and implement Kruskal's algorithm.
#include <vector>
#include <map>
#include <iostream>
#include "SetElement.h"
using namespace std;
// Forward declaration of the vertex class. Needed to resolve
// circular dependence between edge and vertex classes.
template <class V,class W>
class vertex;
template <class V,class W>
class edge
{
public:
edge(vertex<V,W> *one,vertex<V,W> *two,const W& wt)
: u(one), v(two), weight(wt) {}
W weight;
vertex<V,W> *u,*v;
};
template <class V,class W>
class vertex : public SetElement
{
public:
vertex(const V& data)
: key(data) {}
V key;
};
template <class V,class W>
class KruskalGraph
{
public:
KruskalGraph() {};
~KruskalGraph();
void readFrom(istream& in);
// Return a pointer to the vertex whose key is 'key'
vertex<V,W>* findVertex(const V& key);
vector<edge<V,W>*> Kruskal();
private:
vector<vertex<V,W>*> vertices; // Pointers to all vertices stored here
map<V,vertex<V,W>*> vMap; // Map used to look up vertices quickly
vector<edge<V,W>*> edges; // Pointers to all edges are store here
vertex<V,W>* makeVertex(const V& key); // Creates the vertex and adds a
// pointer to it to both vertices and vMap
};
Note that in this graph structure none of the vertices contain lists of edges. Instead, each edge contains pointers to the two vertices it joins, and the graph itself contains a vector of pointers to edges. The KruskalGraph class contains a Kruskal() method that computes and returns a list of pointers to edges that form a minimum spanning tree.
The file format we will use for our graph is essentially a list of edges. For example, for the graph depicted here
|
the file representation will be
a b 6 a c 5 b c 9 b e 13 c d 16 c f 12 d e 15 d f 7 e g 8 f g 3
As part of the process of reading the graph structure from a text file, you will need to make use of the findVertex and makeVertex member functions. These are very similar in style to the methods I have already written for earlier graph examples I posted. See those earlier examples for details.
Your assignment is to write the necessary methods needed to make the KruskalGraph class fully functional. Write a test program to go along with these classes that reads a graph from a file, computes a minimum spanning tree for the graph, and then prints the edges in the minimum spanning tree to cout.