A Brief Introduction To Greedy Algorithms

Greedy is an algorithmic approach to create a solution step-by-step. Always select the next step which provides the most obvious and immediate result. They are extremely useful in optimization problems. A problem having a property that, at every step, we can make the best choice for that moment and get the optimized solution for the entire problem. Greedy algorithms are more efficient than any other algorithm. But the problem with them is that they cannot be always applied. Here are some standard greedy algorithms :

Kruskal’s Minimum Spanning Tree (MST): In this algorithm, we an MST is created by picking edges one by one. The choice is made on the basis of the weight of edges. Hence, we pick the edge having smallest weight and which don’t cause a cycle in the created MST.

Prim’s Minimum Spanning Tree: This algorithm is also based on picking the edges one by one to create MST. However, in this algorithm, we create two sets. One for vertices that have been included in MST and the other one is for the vertices that are not included yet. We pick the smallest weight vertices to connect the two sets.

Dijkstra’s Shortest Path: It is very similar to the previous Prim’s algorithm. The shortest path tree is created using vertices. Also, maintain the two sets of vertices one that contains the vertices included in the tree and the other one with the vertices that are not yet included. The choice here is the smallest weight path vertice from source to the set that contains the vertices that are not yet included.

Huffman Coding: Huffman Coding algorithm is a compression technique. It assigns variable length bit code to every different character. The basic idea is to assign least bit length code to the frequently occurring character. The more frequently a character is occurring, we will try to assign the least lengthy bit code.