Question

What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in an optimal substructure.

Answer 1

Definition of Greedy Algorithm:

• An algorithm is designed to achieve optimum solution for a given problem.Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions.
• However, generally greedy algorithms do not provide globally optimized solutions.thats why it is a optimal substructure.

Two conditions define the Greedy Paradigm:

1. Each stepwise solution must structure a problem towards its best-accepted solution.
2. It is sufficient if the structuring of the problem can halt in a finite number of greedy steps

Use of Greedy Approach:

• One prominent reason is to achieve the most feasible solution immediately. In the activity selection problem , if more activities can be done before finishing the current activity, these activities can be performed within the same time

Examples of Greedy Approach :

• Most networking algorithms use the greedy approach. Here is a list of few of them

1. Kruskal's Minimal Spanning Tree Algorithm.
2. Prim's Minimal Spanning Tree Algorithm.
3. Knapsack Problem
4. Job Scheduling Problem

Now why greedy choice been made by kruskal's algorithm:

Introduction on kruskal's algorithm:

Kruskal’s algorithm uses the greedy approach for finding a minimum spanning tree.Kruskal’s algorithm treats every node as an independent tree and connects one with another only if it has the lowest cost compared to all other options available.

Important Point: To Know Why Kruskal's Algorithm is Greedy Approach:

The Krushkal's algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far.

Step to Kruskal’s algorithm:

Step 1: Sort the graph edges with respect to their weights.

Step 2: Start adding edges to the minimum spanning tree from the edge with the smallest weight until the edge of the largest weight.

Step 3: Only add edges which don’t form a cycle—edges which connect only disconnected components.

[OR]

In Simpler Form Explaination:

Step 1 – Remove all loops and parallel edges

Step 2 – Arrange all the edges in ascending order of cost

Step 3 – Add edges with least weight

Now, Why Greedy Algorithm is Optimal Substructure:

First let us know what is optimal substructure:

Optimal Substructure: A problem has an optimal substructure if its optimal solution can be constructed from the optimal solutions of its subproblems.

• Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions.thats why Greedy Algorithm is optimal Substructure.