Q4(a). Define the following term: Greedy method, optimal solution, Minimum spanning tree . Describe the paradigm of greedy method. Which types of algorithm does it address? At which situations can it be used?
Q4(b). Use Kruskal’s algorithm to find the minimum spanning tree for the following graph which is shown in Figure 3 and Draw your spanning tree.
Answers
Answer:
Greedy algorithms build a solution part by part, choosing the next part in such a way, that it gives an immediate benefit. This approach never reconsiders the choices taken previously. This approach is mainly used to solve optimization problems.
An optimal solution is a feasible solution where the objective function reaches its maximum (or minimum) value – for example, the most profit or the least cost. A globally optimal solution is one where there are no other feasible solutions with better objective function values.
A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree. An example is a cable company wanting to lay line to multiple neighborhoods; by minimizing the amount of cable laid, the cable company will save money. A tree has one path joins any two vertices.
Explanation:
hope this helps...