Class KruskalMinimumSpanningTree<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Kruskal's minimum-spanning-tree algorithm: edges are considered in ascending weight order and accepted when they join two different components, tracked with a union-find structure. Naturally yields a spanning forest on disconnected graphs; negative weights are fine.

public sealed class KruskalMinimumSpanningTree<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

KruskalMinimumSpanningTree<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

KruskalMinimumSpanningTree(Func<TEdge, TWeight>)

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

public KruskalMinimumSpanningTree(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.