## Description

1 Project Description

In this project, you implement the Minimum Spanning Tree (MST) of a weighted undirected graph, using

the Kruskal’s algorithm. We consider the nodes in the graph to be numbered from 0 to n – 1. This means

a graph with 4 nodes, has nodes named 0, 1, 2 and 3. Each edge has a weight (a positive number of double

type) associated with it. You will be implementing the Kruskal’s algorithm using Disjoint sets, a wellknown data structure for grouping n elements (nodes) into a collection of disjoint sets (connected

components).

2 How to Represent a Graph

Represent your graph using an adjacency list in which vertices are stored as objects, with every vertex

storing a list of adjacent vertices.

3 How to Test Your Program

We use drivers and tester classes for automated marking, and provide them for you to use while you build

your solution. We also provide you with basic test cases, which can serve as a sample for you to create

more comprehensive test cases. You can find the testing files on the course website.

4 How to Submit Your Program

Once you have completed your solution, and tested it comprehensively, you need to build a compressed

file, in tar.gz format, which should contain the file:

• Weighted_graph.h

• Disjoint_sets.h

Build your tar file using the UNIX tar command as given below:

• tar –cvzf xxxxxxxx_pn.tar.gz Weighted_graph.h Disjoint_sets.h

where xxxxxxxx is your UW user id (ie. jsmith), and n is the project number which is 4 for this project. All

characters in the file name must be lowercase. Submit your tar.gz file using LEARN, in the drop box

corresponding to this project.

5 Class Specifications

In this project, you will implement two classes: Weighted_graph.h, which represents a weighted

undirected graph, and Disjoint_sets.h a disjoint sets data structure.

5.1 Weighted_graph.h

The Weighted_graph class represents a weighted undirected graph. One of its methods obtains the

minimum spanning tree of a graph, using Kruskal’s algorithm.

Member Variables

You need to include here a member variables required to represent an adjacency list. You will also need

other member variables to fully represent the properties of this graph (such as the degree of each node).

Constructor

Weighted_graph ( int n = 10 ) – Constructs a weighted undirected graph with n vertices (by default 50).

Assume that initially there are no connections in the graph (edges will be inserted with the “insert”

method). Throw an illegal_argument exception if the argument is less than 0.

Destructor

~ Weighted_graph () – Cleans up any allocated memory.

2

Accessors

The class has three accessors:

• int degree( int n ) const – Returns the degree of the vertex n. Throw an illegal_argument

exception if the argument does not correspond to an existing vertex.

• int edge_count() const – Returns the number of edges in the graph.

• std::pair<double, int> minimum_spanning_tree() const – Uses Kruskal’s algorithm to find the

minimum spanning tree. It returns the weight of the minimum spanning tree and the number of

edges that were tested for adding into the minimum spanning tree. Use Disjoint sets to ensure that

the Kruskal’s algorithm does not form loops in the tree.

Mutators

The class has three mutators:

• bool insert_edge( int i, int j, double w ) – If i equals j and are in the graph, return false. Otherwise,

either add a new edge from vertex i to vertex j or, if the edge already exists, update the weight and

return true. Recall that the graph is undirected. If i or j are outside the range of [0..n-1] or if the

weight w is less than or equal to zero, throw an illegal_argument exception.

• bool erase_edge( int i, int j ) – If an edge between nodes i and j exists, remove the edge. In this

case or if i equals j return true. Otherwise, if no edge exists, return false. If i or j are outside the

range of [0..n-1], throw an illegal_argument exception.

• void clear_edges() – Removes all the edges from the graph.

5.2 Disjoint_sets.h

To build the minimum spanning tree T, the Kruskal’s algorithm adds one edge to the T (initialized with an

empty graph) in each step. To make sure that this procedure does not form loops in the tree, we need to

keep track of the connected components of T. Disjoint sets is a well-known data structure for grouping n

elements (nodes) into a collection of disjoint sets (connected components). In this project, the goal is to

implement the disjoint sets data structure using linked list (you can read more information on disjoint sets

from Chapter 21 of CLRS book).

Member Variables

This class has at least the following member variables:

• ll_entry* nodes: An array of pointers that keeps a pointer to each node entry in the linked lists.

• set_info* sets: An array of pointers that keeps the information for each set. This information

includes the pointers to head and tail of the set as well as an integer that keeps the size of the set.

• int set_counter: A variable that saves the current number of sets.

• int initial_num_sets: A variable that saves the initial number of sets.

Constructor

Disjoint_sets(int n) – Constructs a disjoint sets data structures with n sets each containing one element

(therefore the total number of elements in n).

Destructor

~Disjoint_sets() – Cleans up any allocated memory.

Accessors

This class has two accessors:

• int num_sets() – Returns the number of sets.

• int find_set(int iitem) – Returns the representative of the set that the node item belongs to.

Mutator

This class has this mutator:

• void union_sets(int node_index1, int node_index2) – Unites the dynamic sets that contain

node_index1 and node_index2.