Greedy algorithm is used to provide the solution piece by piece always choosing the next piece that offers the most obvious and immediate benefits. So, the problems were choosing locally optimum solution for that time. In this, the decision is taken on the basis of current available information without worrying about the effect of the current decision in future. In greedy algorithm, we decide at every state that what we have to choose so that it could become optimum. There are some advantages of greedy algorithm.
- Greedy algorithm is quite easy to solve a problem.
- Analyzing the run time for greedy algorithms will generally be much easier than for other techniques (like Divide and conquer). Because in divide and conquer size of subproblem increases every time.
- Example.
- Finding the shortest path between two vertices using Dijkstra’s algorithm.
- Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm, etc.
Prim’s Minimal Spanning tree:
In Prim’s Minimal Spanning Tree, a spanning tree means all vertices must be connected. So, the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
Algorithm
1) Create a set Set that keeps track of vertices already included in MST(minimal spanning tree).
2) Assign a key value to all vertices in the graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it could be picked first.
3) While Set doesn’t include all vertices
- a)Pick a vertex u which is not there in Set and has minimum key value.
b) Include u to Set. - c)Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v.
The key values are used only for vertices which are not yet included in MST, the key value for these vertices indicates the minimum weight edges connecting them to the set of vertices included in MST.
