Algorithms For Dummies

 

»

Kruskal’s Minimum Spanning Tree (MST): This algorithm actually demon-

strates one of the principles of greedy algorithms that people might not think 

about immediately. In this case, the algorithm chooses the edge between two 

nodes with the smallest value, not the greatest value as the word greedy might 

initially convey. This sort of algorithm might help you find the shortest path 

between two locations on a map or perform other graph-related tasks.

 

»

Prim’s MST: This algorithm splits an undirected graph (one in which direction 

isn’t considered) in half. It then selects the edge that connects the two halves 

such that the total weight of the two halves is the smallest that it can be. You 

---

32

 

   

  PART 1