8.2. Prim's Algorithm
This section discusses Prim's Algorithm that finds a minimum spanning tree in an undirected graph.
Prim's algorithm finds a minimum spanning tree by finding the minimum edge among all incoming edges of visited vertices.
Let us define the MSTPrim
class inheriting the MST
interface:
L9
: adds the vertex0
to the visited set and its incoming edges to the queue.L11
: iterates through all incoming edges:L14
: if the visited set contains the source vertex, adding the edge would create a cycle.L16
: if the tree containsv-1
number of edges, a spanning tree is found.L17
: repeats the process by adding the source of the edge.
The add()
method can be defined as follows:
L4-7
: adds all incoming edges that have not been visited to the queue.
What is the worst-case complexity of Prim's Algorithm?
Last updated