Question

_ is known as greedy algorithm.Becausr it choose at each step the cheapest edge to add to subgraph s.

Answer 1

Kruskal’s algorithm

Explanation:

Kruskal’s algorithm is known as greedy algorithm, because it choose at each step the cheapest edge to add to subgraph S.

Kruskal's Algorithm refers to finding the minimum spanning tree for a connected weighted graph. It's just like finding individual tree in a forest at every node. A tree connects to another only and only if, it has the least cost among all available options and does not violate MST properties.  

The aim is to find the subset of edges by using which, we can traverse every vertex of the graph.  

ALGORITHM

Step 1: Create a forest in such a way that each graph is a separate tree.  

Step 2: Create a priority queue Q that contains all the edges of the graph.  

Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY  

Step 4: Remove an edge from Q  

Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest (for combining two trees into one tree).  

ELSE  

Discard the edge  

Step 6: END