Class PrimMinimumSpanningTree<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Prim's minimum-spanning-tree algorithm (lazy variant): each tree grows from a root by repeatedly taking the cheapest edge crossing the frontier, using a priority queue. Every connected component gets its own tree, so disconnected graphs yield a spanning forest; negative weights are fine.

public sealed class PrimMinimumSpanningTree<TVertex, TEdge, TWeight> : IMinimumSpanningTreeAlgorithm<TVertex, TEdge, TWeight> where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Inheritance

object

PrimMinimumSpanningTree<TVertex, TEdge, TWeight>

Implements

IMinimumSpanningTreeAlgorithm<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

PrimMinimumSpanningTree(Func<TEdge, TWeight>)

Initializes the algorithm with the function that reads an edge's weight.

public PrimMinimumSpanningTree(Func<TEdge, TWeight> weightSelector)

Parameters

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Exceptions

ArgumentNullException

weightSelector is null.

Methods

FindMinimumSpanningForest(IReadOnlyGraph<TVertex, TEdge>)

Computes a minimum spanning forest of the graph.

public IReadOnlyList<TEdge> FindMinimumSpanningForest(IReadOnlyGraph<TVertex, TEdge> graph)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The undirected graph to span.

Returns

IReadOnlyList<TEdge>

The chosen edges: |V| - #components of them, total weight minimal.

Exceptions

ArgumentException

graph is directed.