Greedy algorithm

Summary

A greedy algorithm builds a solution step by step, at each step making the choice that looks best at that moment and never revising it. Greedy algorithms are simple and fast, but they find an optimal solution only for problems with special structure. For choosing a maximum-weight independent set, the greedy rule is optimal for every weight function exactly when the independent sets form a matroid. Kruskal's algorithm, Prim's algorithm and Dijkstra's algorithm are greedy.