Saturday, April 2, 2011

Kruskal algorithm, my implementation


  • Today I decided to code my own implementation of the Kruskal algorithm, based on the description found in profesor Zaragoza's notes
    slides 234 through 252

  • This is the graph I'm using:


which I found here:







[sourcecode language="cpp"]
#include <iostream>
#include <algorithm>
using namespace std;
const int NUM_VERTEXES = 5;
const int NUM_EDGES = 8;
int edgesA[NUM_EDGES][3] = {{1,2,7},{1,4,8},{1,5,9},{2,3,11},{2,4,3},{2,5,9},{3,4,2},{4,5,5}};
bool tree[NUM_EDGES] = {false};
struct vertex{
int vNum;
struct vertex* father;
int count;
}vertexes[NUM_VERTEXES];
struct edge{
int start;
int end;
int cost;
}edges[NUM_EDGES];
struct vertex* vPtrs[NUM_VERTEXES];
bool operator<(const edge a, const edge b){
return a.cost < b.cost;
}
void initStructure(){
for(int i=0; i<NUM_VERTEXES; i++){
vertexes[i].vNum = i+1;
vertexes[i].father = NULL;
vertexes[i].count = 1;
vPtrs[i] = &vertexes[i];
}
for(int i=0; i<NUM_EDGES; i++){
edges[i].start = edgesA[i][0];
edges[i].end = edgesA[i][1];
edges[i].cost = edgesA[i][2];
}
}
struct vertex* search(struct vertex* n){
vertex* temp;
temp = n;
while(temp->father != NULL){
temp = temp->father;
}
return temp;
}
void join(int i, int j,int edge){
vertex* iPtr = search(vPtrs[i]);
vertex* jPtr = search(vPtrs[j]);
if(iPtr != jPtr){
tree[edge] = true;
if(iPtr->count <= jPtr->count){
iPtr->father = jPtr;
jPtr->count += iPtr->count;
}
else{
jPtr->father = iPtr;
iPtr->count += jPtr->count;
}
}
}
int main(){
initStructure();
sort(edges,edges+NUM_EDGES);
for(int i=0; i<NUM_EDGES; i++){
join(edges[i].start-1,edges[i].end-1,i);
}
for(int i=0; i<NUM_EDGES; i++)
if(tree[i]== true){
cout<<char(edges[i].start+64)<<" "<<char(edges[i].end+64)<<endl;
}
return 0;
}
[/sourcecode]

I'm using a customized format for the edges, one improvement is to parse to that format from a typical adjacency matrix or adjacency list eliminating redundant edges.

Things I learned from this exercise:

  • To use consistent subscript ranges, gosh.. debugging the typical out of bounds error is the lamest thing in the world.

  • To better use a debugger.

  • Operator overloading. Read about it before, but never used it in a program.

  • The different flavors of the sort function in <algorithm>

  • A better understanding of pointers.


My goal in these holydays is to code all the algorithms we reviewed in the algorithms analysis class.

No comments:

Post a Comment