Week 5: Graph Algorithms (40)

Minimum Spanning Trees (cont)

Brute force solution:

findMST(G):
|  Input  graph G
|  Output a minimum spanning tree of G
|
|  bestCost=∞
|  for all spanning trees t of G do
|  |  if cost(t)<bestCost then
|  |     bestTree=t
|  |     bestCost=cost(t)
|  |  end if
|  end for
|  return bestTree

Example of generate-and-test algorithm.

Not useful because #spanning trees is potentially large (e.g. n^n-2 for a complete graph with n vertices)