Question 4

How many method will solve a minimum spanning tree problem?

There are TWO methods to solve a minimum spanning tree problem.

Method One - Prim's algorithm

1. Pick a starting vertex (the things you are connecting), this can be any vertex on your graph as a minimum spanning tree will join all of the vertices together.
2. Look at the edges which connect to this point and choose the one with the lowest value. You will now have two vertices joined together, this is the start of your spanning tree.
3. Look at all the edges connecting to your spanning tree and select the edge of least value to add to your spanning tree.
4. Repeat the above step until all of your vertices have been included in the minimum spanning tree. If the edge of least value is between two vertices already in your minimum spanning tree ignore it as this edge is unnecessary and you would no longer have a minimum spanning tree. 

Method Two - Kruskal's algorithm

1. Look at your graph and find the edge with the least weight (smallest value).

2. From the edges remaining, pick the edge with least weight which does not create a cycle (a closed loop and therefore not a spanning tree) with your other edges.

3. Count the vertices and minus one. This is how many edges you should use. Repeat step 2 until you have selected this number of edges.

    Reference URL ==> http://www.wikihow.com/Find-the-Minimum-Spanning-Tree-of-a-Graph