Greedy Algorithms
Make locally optimal choices at each step to find a global optimum. 4 programs in C with full explanations for VTU BCSL40A.
Greedy Algorithms
T: O(E log E)
S: O(V)
Kruskal's Algorithm
Kruskal's algorithm finds the Minimum Spanning Tree of a weighted graph by sorting edges and using union-find to avoid cycles.
View Algorithm
Greedy Algorithms
T: O(V²)
S: O(V)
Prim's Algorithm
Prim's algorithm builds a Minimum Spanning Tree by greedily expanding from a starting vertex, always picking the minimum cost edge to an unvisited vertex.
View Algorithm
Greedy Algorithms
T: O(V²)
S: O(V)
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
View Algorithm
Greedy Algorithms
T: O(n²)
S: O(1)
Greedy (Fractional) Knapsack
The Fractional Knapsack problem uses a greedy approach — selecting items by highest value-to-weight ratio — allowing fractional items to maximize profit.
View Algorithm