Fundamentals of Programming - 2

1. Sort the edges in increasing order.
2. Start adding edges in the above order ignoring an edge if it forms a cycle with previously chosen edges.
3. Stop when all vertices have been connected. You will choose exactly n-1 edges, where n=number of vertices. (Prove!)

Algorithm 2

1. Pick an arbitrary vertex,v and consider the set S = {v}.
2. Find the smallest edge incident on v. Suppose this edge is (v,w), add w to S.
3. Repeat the previous step (n-2) times. i.e. In each iteration pick the smallest edge coming out of S and add the vertex "at the other end" to S.
   
   Q: Why do you need to iterate n-2 times ?
   
   
   

Algorithm 3

1. For every vertex pick the smallest edge incident on it. This will result in 1 or more "connected components".
2. If the number of connected components is 1 then there is nothing left to do. If there are 2 or more of them, coalesce each component into a single "supervertex". You now have a collection of 2 or more supervertices.
3. Construct a new graph on the supervertices, connecting each pair of supervertices (say V,W), with the minimum edge that connects some vertex in V to some vertex in W. Repeat step 2 for this new graph.

Algorithm for finding shortest path between vertices s,t.

1. Start with the set S={s} and assign "weights" to every vertex as follows : Weight(s)=0, Weight(v)=infinity if there is no edge between v and s, otherwise Weight(v) = length(v,s).
2. Pick the vertex outside S which has the smallest weight and add it to S. If this vertex happens to be t then stop, otherwise go to step 3.
3. Let v1 denote the vertex chosen in the previous step. For every vertex (say w) which lies outside S, do the following : if there is no edge connecting w to v1, do nothing. Otherwise if Weight(w) > (Weight(v1) + length(v1,w)) then change Weight(w) to the right hand side of the above inequality. Go to step 2