Algorithms For Dummies

Discovering the correct algorithms to use

You can find many different algorithms to use to create a minimum spanning tree. 

The most common are greedy algorithms, which run in polynomial time. Poly­

nomial time is a power of the number of edges, such as O(n

2

) or O(n

3

) (see Part 5 for 

additional information about polynomial time). The major factors that affect the 

running speed of such algorithms involve the decision-making process — that is, 

FIGURE 9-2: 

The example 

graph becomes 

weighted.

---

186

 

   

  PART 3 

 Exploring the World of Graphs

whether a particular edge belongs in the minimum spanning tree or whether the 

minimum  total  weight  of  the  resulting  tree  exceeds  a  certain  value.  With  this 

in mind, here are some of the algorithms available for solving a minimum span-

ning tree: