?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Easy

Determining the Minimum Spanning Tree Algorithm

ALGOR-GRA9GQ

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?

A

Kruskal's Algorithm

B

Dijkstra's Algorithm

C

Prim's Algorithm

D

Reverse-Delete Algorithm