- 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