Class PrimMstFinder
A IMstFinder implementing Prim's algorithm.
Inheritance
Implements
Inherited Members
Namespace: MoreStructures.Graphs.MinimumSpanningTree
Assembly: MoreStructures.dll
Syntax
public class PrimMstFinder : IMstFinderRemarks
ALGORITHM
- The algorithm closely resembles Dijkstra's algorithm for shortest distance finding. It is a gready algorithm
selecting a vertex and the corresponding edge at each iteration, and doing that efficiently thanks to the use
of a priority queue and a dictionary of mappings from vertices to edges of shortest distance.
- The core idea is to split the vertices of the graph into two sets: the set A of vertices already added to the
Minimum Spanning Tree MST, and the set NA of vertices which haven't been added yet to the MST.
- At the beginning an arbitrary vertex (id = 0), is included in A and set as last added vertex LA, to bootstrap
the process. The set of edges representing the Minimum Spanning Tree, MST, is set to an empty set. The
dictionary mapping vertices to shortest distance edges BP is set to an empty dictionary. A min priority queue
of vertices, PQ, is also instantiated.
- After that the main loop of the algorithm is executed, adding a single vertex LA to A and a single edge to
MST at each iteration, and stopping only when A contains v vertices (i.e. when MST is spanning the entire
graph).
- At each iteration, all edges e, outgoing from and incoming into LA, and connecting LA to a vertex V not yet
in A are checked.
- If the distance of e, d(e), is strictly smaller than the smallest known edge for V, BP[V], BP is updated and
pushed or updated in PQ.
- After all edges of LA are checked, the vertex V' connected to A via an edge E' of shortest distance is
extracted from PQ, assigned to LA and added to A. E' is added to MST.
- After v - 1 iterations, MST is returned as result.
COMPLEXITY
- All data structures initialization (A, NA, PQ, BP, MST) takes constant amount of time.
- During the v - 1 iterations, all edges are visited at most twice: once from the source side and once from the
target side.
- While checking and updating BP and A take a constant amount of time, pushing or updating the priority in PQ
has a runtime which depends on the specific implementation of IUpdatablePriorityQueue<T> used.
- The analysis of the impact of the priority queue on the overall performance of the algorithm is similar to
the one done in DijkstraShortestDistanceFinder. Check that analysis for
further details.
- In conclusion, Time Complexity is O(e + v * log(v)) with the best available implementation of an
IUpdatablePriorityQueue<T> and O((v + e) * e) with a naive implementation.
- Space Complexity is O(v), since all data structures contains O(v) items, all of constant size.
Constructors
| Improve this Doc View SourcePrimMstFinder(Func<IUpdatablePriorityQueue<Int32>>)
Declaration
public PrimMstFinder(Func<IUpdatablePriorityQueue<int>> priorityQueueBuilder)Parameters
| Type | Name | Description |
|---|---|---|
| Func<IUpdatablePriorityQueue<System.Int32>> | priorityQueueBuilder | A builder of a IUpdatablePriorityQueue<T> of System.Int32 values, used by the algorithm to store edges with priority from the closest to any of the vertices of the MST, to the farthest. |
Methods
| Improve this Doc View SourceFind(IGraph, IGraphDistances)
Finds the Minimum Spanning Tree (MST) of the provided graph using the Prim's algorithm.
Declaration
public ISet<(int, int)> Find(IGraph graph, IGraphDistances distances)Parameters
| Type | Name | Description |
|---|---|---|
| IGraph | graph | |
| IGraphDistances | distances |
Returns
| Type | Description |
|---|---|
| ISet<System.ValueTuple<System.Int32, System.Int32>> |