?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Difficult

Implementing Prim's Algorithm

ALGOR-WB5YXR

You are put in charge of implementing Prim's Algorithm so that you can find a graph's minimum spanning tree.

Which of the following implementations is the most efficient way to implement this algorithm correctly?

A

A 2-dimensional array where the graph's nodes are the rows and columns of the array. An index in the array has a value equal to the weight of the edge if one exists between the row node and the column node and a 0 otherwise.

The edges are chosen based on​ of which edge is the cheapest one that will connect a new node to the connected component surrounding the starting node.

B

A Union-Find data structure where the Union operation is used to connect the connected components of two nodes when the edge between them is added to the minimum spanning tree and the Find operation determines if two nodes are part of the same connected component.

Unions are done in order of increasing edge weight.

C

A Union-Find data structure where the Union operation is used to group the set of edges that have been added to the minimum spanning tree so far and the Find operation determines if adding a certain edge will create a cycle.

Unions are done in order of increasing edge weight.

D

A priority queue where the edges in the priority queue are ordered based on their weight in the graph.

Edges are chosen in order of increasing weight.

E

A priority queue where the nodes in the priority queue are ordered based on the minimum cost that is required to connect the node to the connected component being built from the starting node.

Nodes are chosen in order of increasing cost.