- You can make a single optimal choice at a given step.
- By choosing the optimal selection at each step, you can find an optimal solution for the overall problem.
- Kruskal's Minimum Spanning Tree (MST): This algorithm actually demonstrates 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 might find this algorithm used in a maze game to locate the shortest distance between the start and the finish of the maze.
- Huffman Encoding: This algorithm is quite famous in computers because it forms the basis for many data-compression techniques. The algorithm assigns a code to every unique data entry in a stream of entries, such that the most commonly used data entry receives the shortest code. For example, the letter E would normally receive the shortest code when compressing English text, because you use it more often than any other letter in the alphabet. By changing the encoding technique, you can compress the text and make it considerably smaller, reducing transmission time.