A greedy algorithm is a type of algorithmic paradigm that follows the problem-solving heuristic of making locally optimal choices at each stage with the hope of finding a global optimum.
• In other words, a greedy algorithm makes the best possible decision at each step without worrying about the consequences in the future. This approach is known as the greedy choice property.
Examples of Greedy Algorithms:
Dijkstra’s Algorithm:
Used to find the shortest path from a source vertex to all other vertices in a weighted graph. At each step, it selects the vertex with the minimum distance.
Kruskal’s Algorithm:
Finds the minimum spanning tree of a connected, undirected graph. It repeatedly adds the edge with the smallest weight, avoiding cycles.
Prim’s Algorithm:
Similar to Kruskal’s, Prim’s algorithm builds a minimum spanning tree by adding the edge with the smallest weight at each step.
Fractional Knapsack:
Given a set of items, each with a weight and a value, the goal is to maximize the total value of items in a knapsack of limited capacity. The greedy choice is to select items with the maximum value-to-weight ratio.
Huffman Coding:
Used for lossless data compression. It builds an optimal binary tree for encoding characters by assigning shorter codes to more frequent characters.
Activity Selection:
In a set of activities with start and finish times, the goal is to select the maximum number of non-overlapping activities. The greedy choice is to select the activity that finishes first.
