Kruskal's Minimum Spanning Tree

Hi, can somebody help me implement Kruskal's Minimum Spanning Tree algorithm? I have Prim's algorithm completed already. I'm not sure how the MST works. Any advice or solutions would be greatly appreciated.

Thanks!

MAIN FILE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// File PrimMain.cpp
// Build together with Prim.h and Prim.cpp
#include "Prim.h"

void getFigure9_2(vector<list<destV> > & alist);

int main(void){
	vector<list<destV> > adjList;
	string answer;
	cout << "Use default graph? (Y/N): ";
	cin >> answer;
	if (answer == "Y" || answer== "y"){
	        getFigure9_2(adjList);
		int tw = PrimsAlg(adjList);
		cout << "The sum of the edge weights in the MST is " << tw << endl;
	}
	else {
		cout << "TODO:  implement reading the adjacency list from a file\n";
		return 1;
	}
}
void getFigure9_2(vector<list<destV> > & alist){
	alist.resize(6); // have 6 vertices
	int i,j,w;
	int data[6][6] = {

					{0,3,0,0,6,5},
					{3,0,1,0,0,4},
					{0,1,0,6,0,4},
					{0,0,6,0,8,5},
					{6,0,0,8,0,2},
					{5,4,4,5,2,0}};
	for (i = 0; i < 6; i++)
		for (j = 0; j < 6; j++)
			if (w = data[i][j])
				alist[i].push_back(destV(char(j+'a'),w));
}



PRIM'S ALGORITHM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "Prim.h"

ostream& operator<<(ostream & o, const vinfo  &vi){
	o << vi.name << "(" << vi.nearv << ",";
	if (vi.dist == INF)
		o << "INF";
	else
		o << vi.dist;
	o << ")";
	return o;
}
bool vinfo_less(const vinfo & vi1, const vinfo &vi2){
	return (vi1.dist > vi2.dist);
}
void printVertices(vector<vinfo> & VR){
	for (vector<vinfo>::iterator vit = VR.begin(); vit != VR.end(); vit++)
		cout << *vit << ", ";
	cout << endl;
}
int PrimsAlg(const vector<list<destV> > & alist){ 
	vector<vinfo> VT,Vremaining; 
	int i,edgeweight,n = alist.size(), totalWeight = 0; 
	vector<bool> VinTree(n,false); 
	vinfo next; 
	char vertex,ustar; 
	destV temp; 
	list<destV>::const_iterator it; 
// Initialize set of tree vertices with the first vertex in the adjacency list 
	vertex = 'a'; 
	VinTree[0] = true; 
	next = vinfo(vertex,'-',0); 
	//VT.push_back(vinfo(vertex,'-',0)); 
	VT.push_back(next); 
	// “Remaining edges” are either adjacent to the first vertex, 
	// or not adjacent to the first vertex 
	for (it = alist[0].begin(); it != alist[0].end(); it++) 
		Vremaining.push_back(vinfo(it->name,vertex,it->weight)); 
 
	for (i = 1; i < n; i++){ // The ones that are not adjacent 
		temp = destV(char('a'+i),0); 
		if (find(alist[0].begin(),alist[0].end(),temp)==alist[0].end()) 
			Vremaining.push_back(vinfo(char('a'+i),'-',INF)); 
		}
	make_heap(Vremaining.begin(),Vremaining.end(),vinfo_less); 
	cout << "Start: " << next  << ", Remaining vertices: "; printVertices(Vremaining); 
	// here is the main loop 
	for (i = 1; i < n; i++){ 
		next = Vremaining.front(); 
		pop_heap (Vremaining.begin(),Vremaining.end(),vinfo_less); 
		Vremaining.pop_back(); 
		VT.push_back(next); 
		ustar = next.name; 
		VinTree[ustar-'a'] = true; 

	const list<destV> &vneighbors = alist[ustar-'a']; 
	bool updatedPriorityQueue = false; 
	for (it = vneighbors.begin(); it != vneighbors.end(); it++) 
	if (!VinTree[(it->name)-'a']){ 
	edgeweight = it->weight; 
	vector<vinfo>::iterator loc = 
	 find(Vremaining.begin(), 
	Vremaining.end(),vinfo(it->name)); 
	if (loc != Vremaining.end() && 
		loc->dist > edgeweight){ 
		loc->nearv = ustar; 
		loc->dist = edgeweight; 
	updatedPriorityQueue = true; 
	} 
 } 
			 if (updatedPriorityQueue) 
		make_heap(Vremaining.begin(),Vremaining.end(),vinfo_less); 
		 cout << "Next: " << next << ", Remaining vertices: "; printVertices(Vremaining); 
 } 
 // totalWeight has been initialized to 0 
	for (vector<vinfo>::iterator VTit = VT.begin(); 
		VTit != VT.end(); VTit++) 
		totalWeight += VTit->dist; 
		return totalWeight; 
}


HEADER FILE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
const int INF = INT_MAX;

// a node in the adjacency list
struct destV{
	char name;
	int  weight;
	destV(char n = '-', int w=0):name(n),weight(w){}
	
	bool operator==(const destV &other) const {
		return (name ==  other.name);
	}
};
// a node in list of "remaining vertices" for the algorithm execution
class vinfo{
private:
	char name;
	char nearv; // name of the nearest tree vertex
	int  dist;	// weight of the corresponding edge
public:
	vinfo(char v1='-', char v2 = '-', int d = INF):
		name(v1),nearv(v2),dist(d){}
	bool operator==(const vinfo & other) const{ 
		return name == other.name;
	}	
friend
	ostream& operator<<(ostream & o, const vinfo  &vi);
friend
	int PrimsAlg(const vector<list<destV> > & alist);
friend
	bool vinfo_less(const vinfo & vi1, const vinfo &vi2);
};
extern int PrimsAlg(const vector<list<destV> > & alist);
You mentioned that you have trouble understanding how minimum spanning trees "work". Are you familiar with the concept of a minimum spanning tree or are you having trouble understanding Kruskal's algorithm for finding one?

-Albatross
Minimum spanning trees are just connected subgraphs that are trees.

Kruskal's algorithm basically askes you to create an identical graph T to the original graph G. "T" only has vertices from "G", but none of the edges. You take all the edges from "G" and put it into a set/list. Then you order that list or set from lowest to highest. You keep adding the least weight edges from the set to "T" (while eliminating the edge from the set) while making sure it doesn't make "T" have cycles/circuit (depending on what book you used, the terminology can be different). Eventually you'll get a minimum spanning tree.

If you're asking us to "implement" an algorithm for you, you're sorely mistaken. You have to do your own homework.
Last edited on
Topic archived. No new replies allowed.