Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsMinimum spanning tree algorithms

Prim's algorithm

The running time

Report a typo

Depending on a representation of a graph and a data structure used to find an edge with the smallest weight, Prim's algorithm may have different running time. Match the boxes with representations of a graph and data structures (on the left) with the corresponding running time (on the right). $V$ is the number of the vertices of the graph, $E$ – the number of the edges.

Match the items from left and right columns

An adjacency list, an additional binary heap

An adjacency matrix, no additional data structure

An adjacency matrix, an additional list or array

O(E\ log\ V)

O(V^3)

O(V^2)

___

Create a free account to access the full topic