Finding the minimum spanning tree of a graph is a problem which has several greedy algorithm solutions. One such algorithm starts with a root node and grows a tree out from there. It does this by choosing the minimum cost edge that will attach a new node in the graph to the tree currently being grown from the root node.

In the first iteration, the algorithm would choose the edge with the least cost that connects the root node s to another node v in the graph. The next iteration would add the least expensive edge that connects the nodes s or v to another node in the graph that is not node s or v.

What is the name of this algorithm?

Select an assignment template