Greedy is an algorithmic approach to solve problems. Greedy algorithms look for locally optimal choice at every step with the objective to find out the most efficient global solutions. This approach may not work in all scenarios though it solves certain problems such as activity selection problem and minimum spanning tree problem. Nevertheless, greedy approach generally solves the problem in reasonable time.
Following are few problems that work well with greedy approach.
- Activity selection problem. Selecting the maximum number of activities that can be done sequentially from the given set of activities.
- Huffman coding algorithm – Lossless compression. Frequency of characters in input text is given. Build a huffman code tree which assigns most frequent character with smaller code. Another useful link.
- Prim’s algorithm for minimum spanning tree. Minimum spanning tree is the set of edges in a weighed graph which touches all the edges in such as way that the overall weigh is minimal.
- Kruskal’s algorithm for minimum spanning tree. Link.
- Prim’s Vs Kruskal’s algorithms – Prim’s algorithm starts with a single vertex and maintains a connected component all the time. At every step it chooses for the vertex with the smallest weight that emerges from the one of the vertices in the connected component. Kruskal’s algorithm uses forest not the connect component. It looks for the edge with the smallest weight that doesn’t form a circuit.
- Dijkstra’s shortest path algorithm.