{"id":93541,"date":"2021-05-11T09:00:52","date_gmt":"2021-05-11T03:30:52","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=93541"},"modified":"2021-05-05T10:19:49","modified_gmt":"2021-05-05T04:49:49","slug":"greedy-algorithm-of-data-structures","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/","title":{"rendered":"Greedy Algorithm of Data Structures"},"content":{"rendered":"<p><span style=\"font-weight: 400;\">Ever wondered how an ATM works? After swiping your card and entering your pin, it asks you to enter the amount you need to withdraw. Now, ATMs have a greedy algorithm that forces these machines to choose the largest denomination possible. <\/span><\/p>\n<p><span style=\"font-weight: 400;\">Suppose there are denominations of \u20b9100, \u20b9200, \u20b9500, and \u20b92000 in a machine and you want to withdraw \u20b97300. Then the greedy approach opted by ATM will be:<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Select three \u20b92000 denomination notes. Remaining amount \u20b91300<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Select two \u20b9500 denomination notes. Remaining amount \u20b9300<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Select one \u20b9200 denomination note. Remaining amount \u20b9100<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Finally, select \u20b9100 denomination note and this solves the problem.<\/span><\/li>\n<\/ul>\n<p><span style=\"font-weight: 400;\">In this article, we will learn about the greedy algorithms, their properties, and the steps to achieve a greedy algorithm design. We will also see some real-life examples of greedy algorithms.<\/span><\/p>\n<h3>Greedy Algorithm<\/h3>\n<p><span style=\"font-weight: 400;\">Greedy algorithms find out many possible solutions and choose the best solution for the problem. In this algorithm, we focus on the individual sub-models of a bigger problem and we try to solve them independently.\u00a0<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Each step-by-step solution must approach the problem towards its best solution possible.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">It may not give an optimal solution.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">The problem where there is no optimal solution possible, the greedy algorithm provides us with a solution that is close to optimal.<\/span><\/li>\n<\/ul>\n<h3>History of Greedy Algorithm<\/h3>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Edsger Dijkstra proposed the concept of greedy algorithms to generate minimum spanning trees. He wanted to short the routes in Amsterdam.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Greedy algorithms were used for multiple walk graph problems in the 1950s.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">American researchers, Cormen, Rivest, and Stein in 1970 put forward a proposal for recursive substructuring of greedy solutions in their book \u201c Introduction to algorithms\u201d.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Many networking protocols like open-shortest-path-first (OSPF) use a greedy approach to minimize time spent on the network.<\/span><\/li>\n<\/ul>\n<h3>Properties required for the Greedy Algorithm<\/h3>\n<p><span style=\"font-weight: 400;\">A greedy algorithm works if the problem is having the following two properties :<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><b>Greedy choice property:<\/b><span style=\"font-weight: 400;\"> We can reach a globally optimized solution by creating a locally optimized solution for each sub-module of the problem.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Optimal substructure:<\/b><span style=\"font-weight: 400;\"> Solutions to subproblems of optimal solutions are also optimal.<\/span><\/li>\n<\/ul>\n<h3>Characteristic of a Greedy Approach<\/h3>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">The resources available have costs attached to them. These are the constraints.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">The greedy approach uses maximum resources in time a constraint applies.<\/span><\/li>\n<\/ul>\n<h3>Steps to achieve Greedy Algorithm<\/h3>\n<ol>\n<li style=\"font-weight: 400;\"><b>Feasible:<\/b><span style=\"font-weight: 400;\"> The algorithm should follow all constraints to return at least one solution to the problem.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Local optimal choice:<\/b><span style=\"font-weight: 400;\"> Make optimum choices from currently available options.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Unalterable:<\/b><span style=\"font-weight: 400;\"> We cannot change a decision at any subsequent point while execution.<\/span><\/li>\n<\/ol>\n<h3>Advantages of Greedy Algorithm<\/h3>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Very few trade-offs compared to other algorithms, make it highly optimized.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">The best solution is reachable immediately since multiple activities can execute in a given time frame.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">No need to combine the solutions of subproblems.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">This algorithm is very easy to describe.<\/span><\/li>\n<\/ul>\n<h3>Failed Greedy Algorithm<\/h3>\n<p>Let us change the above example by a bit. Let us assume that we now have only denominations of \u20b9100, \u20b9700, and \u20b91000. Now if we use the greedy algorithm, to withdraw \u20b91500, we will get one \u20b91000 denomination note and five \u20b9100 denomination notes. Total 6 notes.<\/p>\n<p>But this is not an optimal solution. If we get two \u20b9700 denominations and one \u20b9100 denomination, we can achieve the task in just 3 notes. This proves that a greedy algorithm does not always provide us with an optimal solution.<\/p>\n<p>Therefore in such cases, the Greedy method can be wrong and sometimes in the worst case even results in a non-optimal solution.<\/p>\n<h3>Applications of Greedy Algorithm<\/h3>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93552\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm.jpg\" alt=\"Common Applications of Greedy Algorithm\" width=\"1000\" height=\"628\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm.jpg 1000w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-300x188.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-150x94.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-768x482.jpg 768w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-720x452.jpg 720w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-520x327.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Common-Applications-of-Greedy-Algorithm-320x201.jpg 320w\" sizes=\"auto, (max-width: 1000px) 100vw, 1000px\" \/><\/a><\/p>\n<h4>1. Fit algorithm in memory management<\/h4>\n<p>Fit memory management algorithms are techniques for allocating the memory blocks to the processes in an operating system.<\/p>\n<p>Here, a pointer keeps track of all the memory blocks and accepts or rejects the request of allocating a memory block to an incoming process. There are three types of fit memory management algorithms:<\/p>\n<ol>\n<li style=\"font-weight: 400;\"><b>First fit algorithm:<\/b><span style=\"font-weight: 400;\"> First sufficient memory block from the top of the main memory is allocated to the process.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Best fit algorithm:<\/b><span style=\"font-weight: 400;\"> Minimum sufficient memory block available in the memory is allocated to the process.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Worst fit algorithm:<\/b><span style=\"font-weight: 400;\"> Largest sufficient memory block available in the memory is allocated to the process.<\/span><\/li>\n<\/ol>\n<h4>2. Scheduling algorithms<\/h4>\n<p>A typical process in a computer has input time, output time, and CPU time. In multiprogramming systems, while one process is waiting for its input\/output the other processes can use the CPU.<\/p>\n<p>Process scheduling algorithms perform these tasks. These algorithms determine which process will use the CPU for execution and which processes will be on hold. These algorithms make sure that the CPU utilization is for maximum time and process execution takes place in minimum time.<\/p>\n<p>Six types of scheduling algorithms are:<\/p>\n<p><b>a. First come first serve:<\/b><span style=\"font-weight: 400;\">\u00a0 In this non-preemptive scheduling algorithm, the processes are executed on a first come first serve basis.<\/span><\/p>\n<p><b>b. Shortest job first:<\/b><span style=\"font-weight: 400;\"> In this non-preemptive scheduling algorithm, the approach is to minimize the waiting time for the process.<\/span><\/p>\n<p><b>c. Priority scheduling:<\/b><span style=\"font-weight: 400;\"> This non-preemptive algorithm assigns each process a priority, and the process with the highest priority is executed first.<\/span><\/p>\n<p><b>d. Shortest remaining time:<\/b><span style=\"font-weight: 400;\"> In this preemptive scheduling algorithm, the process which has the least time remaining for its completion is executed first.<\/span><\/p>\n<p><b>e. Round robin scheduling:<\/b><span style=\"font-weight: 400;\"> In this preemptive process scheduling algorithm, each process is provided a fixed time to get executed. If the process is not completely executed, it will be assigned the same time for execution in the next round.<\/span><\/p>\n<p><b>f. Multiple level queue schedule:<\/b><span style=\"font-weight: 400;\"> These are not independent scheduling algorithms. Programmers make many queues for processes with common characteristics and every queue can have its own scheduling algorithm.<\/span><\/p>\n<h4>3. Bin packing problem<\/h4>\n<p>We need to pack items of different volumes into a finite number of bins of fixed volume each in such a way that we use the minimum number of bins. Placing data on multiple disks and loading containers like trucks are some real-life examples of this algorithm.<\/p>\n<h4>4. Travelling salesman problem<\/h4>\n<p>Given a set of cities and distance between every pair of the city, the objective is to find the shortest possible path to visit each city exactly once and return to the starting point.<\/p>\n<h4>5. Fractional knapsack problem<\/h4>\n<p>Imagine you have different items with their weights and their values. Our objective is to determine the subset of items that we should include in a collection so that their total weight is less than or equal to a given limit and their value is maximum. The fractional knapsack problem is an optimization problem.<\/p>\n<h4>6. Minimum spanning trees<\/h4>\n<p>Minimum spanning tree is a subset of the edges from starting to end in a weighted and undirected graph. MST connects all vertices without any cycle and the total weight of all the edges included is minimum..<\/p>\n<h4>7. Dijkstra shortest path algorithm<\/h4>\n<p>Finding the shortest path between two vertices in a graph such that the sum of weights between the edges is minimum.<\/p>\n<h4>8. Egyptian fraction<\/h4>\n<p>We can represent every positive fraction as a sum of unique unit fractions. For example, the Egyptian fraction representation of 47\/154 is 1\/7 + 1\/11 + 1\/14.<\/p>\n<h3>Problems solved by the Greedy Approach<\/h3>\n<h4>1. Activity search problem<\/h4>\n<p><span style=\"font-weight: 400;\">The activity search problem is a mathematical search optimization problem. This is used in scheduling a single resource among several ongoing and incoming processes. A greedy algorithm provides the best solution for selecting the maximum size set of compatible activities.<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Let S =\u00a0 {1,2,3,&#8230;n) be a set of n proposed processes. Resources can be used by only one process at a time. Start time of activities = {s<\/span><span style=\"font-weight: 400;\">1<\/span><span style=\"font-weight: 400;\">,s<\/span><span style=\"font-weight: 400;\">2<\/span><span style=\"font-weight: 400;\">,s<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\">,&#8230;.s<\/span><span style=\"font-weight: 400;\">n<\/span><span style=\"font-weight: 400;\">} and finish time = {f<\/span><span style=\"font-weight: 400;\">1<\/span><span style=\"font-weight: 400;\">,f<\/span><span style=\"font-weight: 400;\">2<\/span><span style=\"font-weight: 400;\">,f<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\">,&#8230;f<\/span><span style=\"font-weight: 400;\">n<\/span><span style=\"font-weight: 400;\">}. Start time is always less than finish time. <\/span><\/p>\n<p><span style=\"font-weight: 400;\">If <\/span><span style=\"font-weight: 400;\">activity &#8220;i&#8221; starts meanwhile the half-open time interval [s<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">, f<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">), then, activities i and j are said to be compatible if the intervals (s<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">, f<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">) and [s<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">, f<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">) do not overlap.<\/span><\/p>\n<p><span style=\"font-weight: 400;\"><strong>Algorithm<\/strong>:<\/span><\/p>\n<p><span style=\"font-weight: 400;\">activity_selector (s, f)<\/span><\/p>\n<p><b>Step 1:<\/b><span style=\"font-weight: 400;\">\u00a0 n \u2190 len[s]<\/span><\/p>\n<p><b>Step 2: <\/b><span style=\"font-weight: 400;\">\u00a0A \u2190 {1}<\/span><\/p>\n<p><b>Step 3:<\/b><span style=\"font-weight: 400;\">\u00a0 j \u2190 1.<\/span><\/p>\n<p><b>Step 4: <\/b><span style=\"font-weight: 400;\">\u00a0for i \u2190 2 to n<\/span><\/p>\n<p><b>Step 5:\u00a0 <\/b><span style=\"font-weight: 400;\">do if s<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\"> \u2265 f<\/span><span style=\"font-weight: 400;\">i<\/span><\/p>\n<p><b>Step 6:<\/b><span style=\"font-weight: 400;\">\u00a0 then A \u2190 A U {i}<\/span><\/p>\n<p><b>Step 7: <\/b><span style=\"font-weight: 400;\">\u00a0j \u2190 i<\/span><\/p>\n<p><b>Step 8:<\/b><span style=\"font-weight: 400;\"> return A<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Example :\u00a0<\/span><\/p>\n<p><span style=\"font-weight: 400;\">S={A1,A2,A3,A4,A5}<\/span><\/p>\n<p><span style=\"font-weight: 400;\">s<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">={1,1,2,3,4}<\/span><\/p>\n<p><span style=\"font-weight: 400;\">f<\/span><span style=\"font-weight: 400;\">i<\/span><span style=\"font-weight: 400;\">={4,2,4,7,6}<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Step 1. Arrange in increasing order of finish time.<\/span><\/p>\n<table>\n<tbody>\n<tr>\n<td><span style=\"font-weight: 400;\">Activity<\/span><\/td>\n<td><span style=\"font-weight: 400;\">A2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">A3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">A1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">A5<\/span><\/td>\n<td><span style=\"font-weight: 400;\">A4<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">s<\/span><span style=\"font-weight: 400;\">i<\/span><\/td>\n<td><span style=\"font-weight: 400;\">1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">f<\/span><span style=\"font-weight: 400;\">i<\/span><\/td>\n<td><span style=\"font-weight: 400;\">2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">7<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93616\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7.png\" alt=\"Greedy Algorithm\" width=\"699\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7.png 699w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7-300x110.png 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7-150x55.png 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7-520x191.png 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/image6-7-320x118.png 320w\" sizes=\"auto, (max-width: 699px) 100vw, 699px\" \/><\/a><\/p>\n<p>Step 2: Schedule A2<br \/>\nStep 3: Schedule A3 (A2, A3 not interfering)<br \/>\nStep 4: Skip A1 (Interfering)<br \/>\nStep 5: Schedule A5 (A2, A3, A5 not interfering)<br \/>\nStep 6: Skip A4 (Interfering)<br \/>\nStep 7:Final Activity schedule is A2, A3, A5.<\/p>\n<h4>2. Fractional Knapsack Problem<\/h4>\n<p>Optimization problem where it is possible to select fractional items rather than binary choices of 0 and 1. The binary problem cannot be solved by a greedy approach.<\/p>\n<p><strong>Step 1:<\/strong> Calculate the value per pound.<\/p>\n<p><strong>Step 2:<\/strong> Take the maximum possible amount of substance with the maximum value per pound.<\/p>\n<p><strong>Step 3:<\/strong> If that amount is exhausted, and we have space, take the maximum possible amount of substance with the next maximum value per pound.<\/p>\n<p><strong>Step 4:<\/strong> Sort the item values per pound, greedy algorithm has a time complexity of O(n log n ).<\/p>\n<p><strong>Algorithm:<\/strong><\/p>\n<p>fractional knapsack (Array w, Array v, int C)<br \/>\n1. for i= 1 to size (v)<br \/>\n2. do vpp [i] = v [i] \/ w [i]<br \/>\n3. Sort-Descending (vpp)<br \/>\n4. i \u2190 1<br \/>\n5. while (C&gt;0)<br \/>\n6. do amt = min (C, w [i])<br \/>\n7. sol [i] = amt<br \/>\n8. C= C-amt<br \/>\n9. i \u2190 i+1<br \/>\n10. return sol<\/p>\n<p><strong>Example:<\/strong><\/p>\n<p>I = { I1,I2,I3,I4}<br \/>\nw={ 20,30,40,50}<br \/>\nv={40,20,70,60}<br \/>\nCapacity, C = 75<\/p>\n<p>Step 1: vpp = { 2,0.66,1.75,1.2}<br \/>\nStep 2: Choose I1. Total weight 20. Left Capacity = 40<br \/>\nStep 3: Choose I3, Total weight 40. Left capacity = 15<br \/>\nStep 4: Choose I4 fractional. Total weight 15. Left capacity = 0<br \/>\nStep 5: value = 40+70+1.2*15 = 128<\/p>\n<h4>3. Huffman Coding<\/h4>\n<p>Huffman coding is used for efficient data encoding for data compression problems.<\/p>\n<p>For example, there are 106 characters in a file but only a few characters appear repeatedly :<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Character\u00a0<\/strong><\/td>\n<td><span style=\"font-weight: 400;\">a<\/span><\/td>\n<td><span style=\"font-weight: 400;\">e<\/span><\/td>\n<td><span style=\"font-weight: 400;\">i<\/span><\/td>\n<td><span style=\"font-weight: 400;\">o<\/span><\/td>\n<td><span style=\"font-weight: 400;\">u<\/span><\/td>\n<\/tr>\n<tr>\n<td><strong>frequency<\/strong><\/td>\n<td><span style=\"font-weight: 400;\">45<\/span><\/td>\n<td><span style=\"font-weight: 400;\">13<\/span><\/td>\n<td><span style=\"font-weight: 400;\">12<\/span><\/td>\n<td><span style=\"font-weight: 400;\">14<\/span><\/td>\n<td><span style=\"font-weight: 400;\">16<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><span style=\"font-weight: 400;\">Expressing the file in a compact way:\u00a0<\/span><\/p>\n<ol>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Fixed length Code: each character is represented by 3 bits per character. For the whole file, we will need 3 <\/span><span style=\"font-weight: 400;\">x 10<\/span><span style=\"font-weight: 400;\">6 <\/span><span style=\"font-weight: 400;\">bits.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">A variable-length code: it assigns long bits for infrequent characters to generate and short bits for frequent characters.<\/span><\/li>\n<\/ol>\n<table>\n<tbody>\n<tr>\n<td><strong>Character\u00a0<\/strong><\/td>\n<td><strong>code<\/strong><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">a<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">e<\/span><\/td>\n<td><span style=\"font-weight: 400;\">101<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">i<\/span><\/td>\n<td><span style=\"font-weight: 400;\">110<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">o<\/span><\/td>\n<td><span style=\"font-weight: 400;\">100<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">u<\/span><\/td>\n<td><span style=\"font-weight: 400;\">111<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Total bits required: ( 45*1+13*4+12*4+14*3+16*3 )*1000 = 210,000 bits.<\/p>\n<h4>Prefix codes<\/h4>\n<p>Prefixes of one encoded character cannot be complete coding to any other character. For example, 100 and 1001 are not valid codes because 100 is a prefix to a code. Prefix codes make encoding and decoding very comfortable.<\/p>\n<p>Algorithm :<\/p>\n<h4>huffman (C)<\/h4>\n<p>1. n=|C|<br \/>\n2. Q \u2190 C<br \/>\n3. for i=1 to n-1<br \/>\n4. do<br \/>\n5. z= allocate-Node ()<br \/>\n6. x= left[z]=Extract-Min(Q)<br \/>\n7. y= right[z] =Extract-Min(Q)<br \/>\n8. arr [z]=arr[x]+arr[y]<br \/>\n9. Insert (Q, z)<br \/>\n10. return Extract-Min (Q)<\/p>\n<h4>4. Travelling Salesman Problem<\/h4>\n<p>Given a set of cities and distance between every pair of the city, the objective is to find the shortest possible path to visit each city exactly once and return to the starting point.<\/p>\n<p>Let there be n cities named, x1,x2,x3,&#8230;..xn. Cij is the cost of traveling from xi to xj. Find the route starting and ending at x1, going through all cities for minimum cost.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93553\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01.jpg\" alt=\"Travelling Salesman Problem\" width=\"1200\" height=\"900\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01.jpg 1200w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-300x225.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-1024x768.jpg 1024w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-150x113.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-768x576.jpg 768w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-720x540.jpg 720w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-520x390.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image01-320x240.jpg 320w\" sizes=\"auto, (max-width: 1200px) 100vw, 1200px\" \/><\/a><\/p>\n<p><strong>Cost adjacency matrix:<\/strong><\/p>\n<table>\n<tbody>\n<tr>\n<td><\/td>\n<td><span style=\"font-weight: 400;\">x1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x5<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x7<\/span><\/td>\n<td><span style=\"font-weight: 400;\">x8<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">7<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">5<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">7<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">7<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x4<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">8<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x5<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">1<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">2<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">8<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">9<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x7<\/span><\/td>\n<td><span style=\"font-weight: 400;\">3<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">x8<\/span><\/td>\n<td><span style=\"font-weight: 400;\">5<\/span><\/td>\n<td><span style=\"font-weight: 400;\">7<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<td><span style=\"font-weight: 400;\">2<\/span><\/td>\n<td><span style=\"font-weight: 400;\">9<\/span><\/td>\n<td><span style=\"font-weight: 400;\">6<\/span><\/td>\n<td><span style=\"font-weight: 400;\">0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Shortest path : x1 -&gt; x5 -&gt; x4 -&gt; x2 -&gt; x3 -&gt;x6 -&gt; x8 -&gt;x7 -&gt; x1<br \/>\nCost : 3 + 1 + 6 + 4 + 6 + 9 + 6 + 3 = 38<\/p>\n<h4>5. Kruskal algorithm<\/h4>\n<p><span style=\"font-weight: 400;\">A minimum spanning tree algorithm finds the subset of graphs which:<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Forms a tree including every vertex.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Has minimum sum of weights among all trees that are possible in a graph<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Kruskal\u2019s algorithm checks if adding an edge creates a loop or not.<\/span><\/li>\n<\/ul>\n<p><span style=\"font-weight: 400;\"><strong>Algorithm<\/strong>:<\/span><\/p>\n<ol>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Sort all edges in ascending order of their weights.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Add the edge with the lowest weight to the spanning-tree<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Keep on adding edges until all the vertices are included.<\/span><\/li>\n<\/ol>\n<p><strong>For example:<\/strong><\/p>\n<p><span style=\"font-weight: 400;\">Using Kruskal\u2019s algorithm, create a minimum spanning tree of the following graph:<\/span><\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93554\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02.jpg\" alt=\"Kruskal Algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image02-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 1<\/strong>: Select an edge with the minimum. If the graph is having multiple minimum weighted edges, you can select any of them.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93555\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03.jpg\" alt=\"Kruskal Algorithm Step\" width=\"350\" height=\"200\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03.jpg 350w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03-300x171.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03-150x86.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image03-320x183.jpg 320w\" sizes=\"auto, (max-width: 350px) 100vw, 350px\" \/><\/a><\/p>\n<p><strong>Step 2:<\/strong> Select the next shortest edge and add it to the tree.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93556\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04.jpg\" alt=\"Kruskal Algorithm Step 2\" width=\"400\" height=\"350\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04.jpg 400w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04-300x263.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04-150x131.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image04-320x280.jpg 320w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/a><\/p>\n<p><strong>Step 3:<\/strong> Select the next shortest edge and add it. The edge should not create a cycle.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93557\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05.jpg\" alt=\"Kruskal Algorithm\" width=\"550\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05.jpg 550w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05-300x218.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05-150x109.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05-520x378.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image05-320x233.jpg 320w\" sizes=\"auto, (max-width: 550px) 100vw, 550px\" \/><\/a><\/p>\n<p><strong>Step 4:<\/strong> Repeat the above steps until we include all the vertices and now you get the spanning tree.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93558\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06.jpg\" alt=\"Kruskal Algorithm \" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image06-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<h4>6. Ford &#8211; Fulkerson algorithm<\/h4>\n<p><span style=\"font-weight: 400;\">A greedy approach that calculates the maximum possible flow in a graph. A flow network has vertices and edges with a source(S) and a sink (T). All vertices can send and receive an equal amount of data but\u00a0 S can only send and T can only receive the data.<\/span><\/p>\n<p><span style=\"font-weight: 400;\">Basic terminologies used in the ford Fulkerson algorithm:<\/span><\/p>\n<ol>\n<li style=\"font-weight: 400;\"><b>Augmenting path:<\/b><span style=\"font-weight: 400;\"> a path that is available in a flow network.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Residual graph:<\/b><span style=\"font-weight: 400;\"> flow network that has an additional possible flow.<\/span><\/li>\n<li style=\"font-weight: 400;\"><b>Residual capacity:<\/b><span style=\"font-weight: 400;\"> capacity of edge after subtracting the flow from maximum capacity.<\/span><\/li>\n<\/ol>\n<p><span style=\"font-weight: 400;\"><strong>Algorithm<\/strong>:<\/span><\/p>\n<ol>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">All flow in the edges is initialized to zero.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">If there is an augmenting path between source and sink, add the path to the flow.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Update residual graph.<\/span><\/li>\n<\/ol>\n<p><span style=\"font-weight: 400;\">Let us analyze this algorithm for a system of pipes with a fixed maximum capacity.<\/span><\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93560\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07.jpg\" alt=\"Ford - Fulkerson algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image07-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 1:<\/strong> Select a path from S to T. Here we select path S -&gt; A -&gt; T<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93559\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08.jpg\" alt=\"Ford - Fulkerson algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image08-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 2:<\/strong> Update the capacities. Here the minimum capacity is of edge A &#8211; T (2).<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93561\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09.jpg\" alt=\"Ford - Fulkerson algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image09-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 3:<\/strong> Select another path. S &#8211; B &#8211; A &#8211; C &#8211; T<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93562\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10.jpg\" alt=\"Ford - Fulkerson algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image10-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 4:<\/strong> Update the capacities again. Here minimum capacity is of the edge S &#8211; B.(3)<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93563\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11.jpg\" alt=\"Ford - Fulkerson algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image11-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p>Add all the flows : 2+3 = 5. This is the maximum flow possible in the flow network.<\/p>\n<h4>7. Dijkstra\u2019s algorithm<\/h4>\n<p>Dijkstra\u2019s algorithm finds the shortest path between the two vertices but it might not include all the vertices of the graph. Dijkstra\u2019s algorithm maintains the distance of every vertex.<\/p>\n<p><strong>For example:<\/strong><\/p>\n<p>Let\u2019s start with a graph:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93564\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12.jpg\" alt=\"Dijkstra\u2019s algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image12-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 1:<\/strong> Select any vertex as starting vertex.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93565\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13.jpg\" alt=\"Dijkstra\u2019s algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image13-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 2:<\/strong> Reach each immediate vertex and update the path distance.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93566\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14.jpg\" alt=\"Dijkstra\u2019s algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image14-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 3:<\/strong> If the adjacent path is greater than the current path, don\u2019t update the path value. Perform step 2 again.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93567\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15.jpg\" alt=\"Dijkstra\u2019s algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image15-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 4:<\/strong> Do not update the path of already visited nodes. To reach any unvisited node, select the path with the minimum path.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93568\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16.jpg\" alt=\"Dijkstra\u2019s algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image16-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<h4>8. Prims algorithm<\/h4>\n<p><span style=\"font-weight: 400;\">A greedy algorithm for minimum spanning tree that takes input in form of a graph and reserves the subset of edges of the graph which<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Forms a tree including every vertex<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Has minimum sum of weight among all the subtrees<\/span><\/li>\n<\/ul>\n<p><span style=\"font-weight: 400;\">Algorithm :<\/span><\/p>\n<ul>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Initialize the minimal spanning tree with any chosen vertex.<\/span><\/li>\n<li style=\"font-weight: 400;\"><span style=\"font-weight: 400;\">Search for all the edges that connect the tree to new vertices, find the minimum from them, and add it to the tree. Perform the system recursively until you get a minimum spanning tree.<\/span><\/li>\n<\/ul>\n<p><strong>For example:<\/strong><\/p>\n<p><span style=\"font-weight: 400;\">Let us consider the graph:-<\/span><\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93570\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17.jpg\" alt=\"Prims algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image17-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<p><strong>Step 1:<\/strong> Select any vertex at random.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image18.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93571\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image18.jpg\" alt=\"Prims algorithm\" width=\"200\" height=\"200\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image18.jpg 200w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image18-150x150.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image18-80x80.jpg 80w\" sizes=\"auto, (max-width: 200px) 100vw, 200px\" \/><\/a><\/p>\n<p><strong>Step 2:<\/strong> Select the shortest edge from this node and add it to the tree.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93572\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19.jpg\" alt=\"Prims algorithm\" width=\"400\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19.jpg 400w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19-300x300.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19-150x150.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19-80x80.jpg 80w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image19-320x320.jpg 320w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/a><\/p>\n<p><strong>Step 3:<\/strong> Choose the nearest vertex which is not included yet.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image20.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93573\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image20.jpg\" alt=\"Prims algorithm\" width=\"300\" height=\"300\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image20.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image20-150x150.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image20-80x80.jpg 80w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/p>\n<p><strong>Step 4:<\/strong> Repeat the above steps recursively until we get the spanning tree.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-93574\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21.jpg\" alt=\"Prims algorithm\" width=\"600\" height=\"400\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21.jpg 600w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21-300x200.jpg 300w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21-150x100.jpg 150w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21-520x347.jpg 520w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21-320x213.jpg 320w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm-image21-272x182.jpg 272w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/a><\/p>\n<h3>Dynamic programming vs Greedy Algorithm<\/h3>\n<table>\n<tbody>\n<tr>\n<td><b>Greedy<\/b><\/td>\n<td><b>Dynamic<\/b><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">We choose which is best and then try to solve the problem arising after it.<\/span><\/td>\n<td><span style=\"font-weight: 400;\">We choose at each step, but it depends on the solution to subproblems.<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">More efficient at finding an optimal solution<\/span><\/td>\n<td><span style=\"font-weight: 400;\">Less efficient at finding an optimal solution<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">Example: fractional knapsack<\/span><\/td>\n<td><span style=\"font-weight: 400;\">Example: 0\/1 knapsack<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">Might or might not get an optimal solution<\/span><\/td>\n<td><span style=\"font-weight: 400;\">Guaranteed optimal solution<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>Conclusion<\/h3>\n<p>We have now seen in this article how greedy algorithms work and the properties required to design the greedy algorithms. We have seen a real-life example where the greedy algorithm fails to give the optimal solution. We have also seen some common real-world applications of algorithms.<\/p>\n<p>Some applications and algorithms were also discussed in this article which has various large implementations in the real world. We will learn about these algorithms in detail in future articles.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Ever wondered how an ATM works? After swiping your card and entering your pin, it asks you to enter the amount you need to withdraw. Now, ATMs have a greedy algorithm that forces these&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":93551,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24203,24201,24202],"class_list":["post-93541","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-applications-of-greedy-algorithm","tag-greedy-algorithm","tag-greedy-algorithm-of-data-structures"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Greedy Algorithm of Data Structures - DataFlair<\/title>\n<meta name=\"description\" content=\"A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. Learn more about this algorithm.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Greedy Algorithm of Data Structures - DataFlair\" \/>\n<meta property=\"og:description\" content=\"A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. Learn more about this algorithm.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-05-11T03:30:52+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"17 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Greedy Algorithm of Data Structures - DataFlair","description":"A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. Learn more about this algorithm.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/","og_locale":"en_US","og_type":"article","og_title":"Greedy Algorithm of Data Structures - DataFlair","og_description":"A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. Learn more about this algorithm.","og_url":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-05-11T03:30:52+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"17 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"Greedy Algorithm of Data Structures","datePublished":"2021-05-11T03:30:52+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/"},"wordCount":2576,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg","keywords":["Applications of Greedy Algorithm","Greedy Algorithm","Greedy Algorithm of data structures"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/","url":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/","name":"Greedy Algorithm of Data Structures - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg","datePublished":"2021-05-11T03:30:52+00:00","description":"A Greedy algorithm makes greedy choices at each step to ensure that the objective function is optimized. Learn more about this algorithm.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Greedy-algorithm.jpg","width":1200,"height":628,"caption":"Greedy algorithm"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/greedy-algorithm-of-data-structures\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"Greedy Algorithm of Data Structures"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/93541","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=93541"}],"version-history":[{"count":7,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/93541\/revisions"}],"predecessor-version":[{"id":93617,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/93541\/revisions\/93617"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/93551"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=93541"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=93541"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=93541"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}