Greedy Algorithms can be and is used in day to day life problems without us even knowing about them.įor Example, Prim’s Algorithm is used for solving various problems like the Travelling salesman Problem, Networks for Roads or Rails, Game development and many more examples that can be solved logically if and when we are giving a dense graph.
Now, let us start by discussing Prim’s Algorithm: As this type of graph is acyclic, thus it is called a Tree. As it is a Greedy Algorithm, thus the vertices should account for the minimum possible weights so as to make a Minimum Spanning Tree.Ī Minimum Spanning Tree is a subgraph of a provided graph that connects all the vertices with the minimum possible number of edges having minimum possible weights with no possible cycles. The basic ideology behind Prim’s Algorithm and Kruskal’s Algorithm is to make a spanning tree that is, all the vertices should be joined with each other. A Greedy Algorithm is such which chooses the next step that offers the maximum and most immediate or optimises the benefit by either minimising it or by maximizing it. Let’s start with the basics first and understand what a Greedy algorithm is and how it works. To Understand Prim’s Algorithm and Kruskal’s Algorithm first we need to discuss what a Greedy Algorithm and a Minimum spanning tree is. Here, we will be covering both Prim’s Algorithm as well as the Kruskal Algorithm approach to obtain a Minimum Spanning Tree. In this blog, we will see how a Greedy Algorithm is used to give a Minimal spanning Tree (MST) works.
0 kommentar(er)
