Home

Decision One

Spanning Tree Problems

Again, you need to be able to know and use these algorithms:

Prim's Algorithm

  1. Start with any vertex
  2. Add in the edge of least weight to start forming a tree
  3. Repeat 2. until all vertices are connnected

Kruskal's Algorithm

  1. Select the edge of smallest weight
  2. Add any [not necessarily connected] edge of minimum weight which doesn't form a cycle
  3. Repeat 2. until all vertices are connected