Greedy Algorithms | Set 6 (Prim’s MST for Adjacency List Representation) – Minimum Spanning Tree – We have discussed Prim’s algorithm and its implement.
Greedy Algorithm
12 Articles
12
Minimum No of Platforms Required for a Railway/Bus Station – Greedy algorithm – Given arrival and departure times of all trains that reach a railway station , to find the minimum number of platforms required for the railway station so that no train waits.
K Centers Problem – Greedy Algorithm – Given n cities and distances between every pair of cities, select k cities to place warehouses ( ATM or Cloud Server)such that the maximum distance of a city to a warehouse is minimized.
Greedy Algorithm to find Minimum number of Coins – Greedy Algorithm – Given a value V, if we want to make change for V Rs. and we have infinite supply of each of the denominations in Indian currency.
Job Sequencing Problem – Greedy Algorithm – Given array of jobs where every job has deadline and associated profit if job is finished before the deadline.
Dijkstra’s Algorithm for Adjacency List Representation – Greedy Algorithm – We have discussed Dijkstra’s algorithm and its implementation for adjacency.In this post, O(ELogV) algorithm for adjacency list representation is discussed.
Dijkstra’s shortest path algorithm – Greedy algorithm – Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root.
Prim’s MST for Adjacency List Representation – Greedy algorithm – We have discussed Prim’s algorithm and implementation for adjacency matrix representation. The time complexity for the matrix representation is O(V^2).
Prim’s Minimum Spanning Tree – Greedy Algorithm – We have discussed Kruskal’s algorithm for Minimum Spanning Tree. Like Kruskal’s algorithm, Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree the idea is to maintain two sets of vertices.
Huffman Coding – Greedy Algorithm – Huffman coding is a lossless data compression algorithm. The idea is to assign variable-legth codes to input characters.