While online I realized that I visit the same sites on a regular basis. So I decided to look through my bookmarks to see what sites I haven't visited in a while. Hey look what I found, SPOJ. Why not try to solve as many problems as I can over this break? I already have bookmarked a few problems I have found to be particularly interesting or will make me implement an algorithm I know but have not coded before.

Well I decided to start with a problem where I was asked to find the minimum spanning tree of a given graph. This falls under the "found to be interesting" category. After thinking about it for a while Dijkstra's Algorithm came to mind, and I said "instead of adding the vertex that has the shortest path to the starting point, why don't I just add the smallest weight?" So I wrote a program to solve the problem this way, with out caring about how efficiency. Then testing it against the example they gave I saw that it worked. So now time to do some improvements, but first to look around the internet (aka Wikipedia) to see what other attacks there are that I might not have considered.

Turns out that the method I though of is known as Prim's Algorithm. Unfortunately the pseudo-code that Wikipedia provided was difficult to follow, but luckily I didn't have to search hard for a site with pseudo-code I could understand. However, there is one thing I still don't understand. Each of the sites mentions how you can put the edges into a heap to help make searching faster. First I don't see how this helps and second how does one decide how one edge comes before another in the heap? Well I guess I'll have more time to consider this.

Here is my implementation of the algorithm, I believe it runs in O(EV) time. Sorry for the horrible formatting, I really wish that blogger would just not auto-format stuff the way MSWord does, so annoying.

void mst(vector&E,int N)

{

vectorfound(N+1,false);//vector of already solved vertices

found[0]=found[1]=true;

long long wgt=0;//total weight

tpl temp=tpl(-1,-1,-1);

while(N-1>0)

{

vector::iterator II=E.begin();

int sh=2000000;

for(vector::iterator I=E.begin();I!=E.end();++I)

{

tpl R=*I;

if(found[R.first]==true && found[R.second]==false)

{

sh=R.third;

temp=R;

II=I;

break;

}

else if(found[R.first]==false && found[R.second]==true)

{

sh=R.third;

temp=R;

II=I;

break;

}

}

N--;

found[temp.first]=found[temp.second]=true;//another vertex has been solved for

wgt+=temp.third;//update total weight

E.erase(II);

print(found);//print found vertices, used to debug

}

printf("%ull\n",wgt);

}

## No comments:

Post a Comment