Class KruskalMstFinder

A IMstFinder based on the Kruskal's algorithm.

Inheritance
System.Object
KruskalMstFinder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.MinimumSpanningTree
Assembly: MoreStructures.dll
Syntax
public class KruskalMstFinder : IMstFinder
Remarks

ALGORITHM
- First, all edges of the graph are sorted in ascending order, using the Sorter provided in the constructor.
- Then, set of edges MST, which will contain the result, is initialized to an empty set (i.e. no edges included in the spanning tree, before the main loop).
- A IDisjointSet DS is also initialized to contain the v values from 0 to v - 1, each value representing a vertex of the graph and at the beginning disjoint from all others.
- The disjoint set DS will be used as a cycle detector, i.e. as a data structure able to determine nearly in O(1) (more precisely in O(log*(n)) whether adding an edge to MST would result in a cycle.
- Then, the main loop of the algorithm is executed, until MST contains exactly v - 1 edges in it (any spanning tree has to have exactly v vertices and v - 1 edges, otherwise it would not be spanning, or it would not be a tree).
- At each iteration, the next minimum edge e is added to MST, if it doesn't introduce a cycle. Otherwise, it is discarded,
- To verify whether e = (u, v) introduces a cycle in MST or not, it checks whether v and u are already connected in DS (via AreConnected(Int32, Int32)), i.e. whether they belong to the same set.
- If so, it means that there is already a path (sequence of edges) in MST connecting u and v. Therefore the introduction of the edge e = (u, v) would give a second path from u to v, hence a cycle.
- Otherwise, e can safely be added to MST with no introduction of a cycle. The vertices u and v are also united in DS, to reflect the addition of e into MST, in DS as well.
- When MST contains v - 1 edges, the number of disjoint sets in DS is checked: if it is 1, it means that all vertices in the graph have been connected by MST, and MST is indeed a Minimum Spanning Tree.
- If it is not the case, and there is more than a single disjoint set, an is thrown, since the graph is not connected, and a single tree spanning the entire graph cannot be constructed.

COMPLEXITY
- The algorithm makes use of an IInputMutatingSort algorithm, to sort all the edges of the graph in ascending order by their distance.
- Since sorting edges is required by the algorithm, the overall complexity is lower bounded by O(e * log(e)) = O(e * log(v)).
- Such complexity can only be reduced when specific assumptions can be made, on the distance values of the edges (e.g. if integer and within a small range, a non-comparison based, linear search, such as Counting Sort, may be used).
- The algorithm also makes use of a IDisjointSet data structure, to detect loops after the potential introduction of each single edge of the graph.
- For that reason, for the algorithm to be efficient, when building the Minimum Spanning Tree, the disjoint set should be able to verify connection (via AreConnected(Int32, Int32)) and to merge vertices (via Union(Int32, Int32)) in (nearly) constant time.
- While this is actually possible, by using a PathCompressionWeightedQuickUnionDisjointSet, the overall complexity is dominated by the edge sorting, which is in general linearithmic over the edges.
- For these reasons, Time Complexity is O(e * log(v)). Space Complexity is O(v + e), since large-enough data structures are required to store sorted edges and disjoint sets of vertices.

Constructors

| Improve this Doc View Source

KruskalMstFinder(IInputMutatingSort, Func<Int32, IDisjointSet>)

Declaration
public KruskalMstFinder(IInputMutatingSort sorter, Func<int, IDisjointSet> disjointSetBuilder)
Parameters
Type Name Description
IInputMutatingSort sorter

Func<System.Int32, IDisjointSet> disjointSetBuilder

Properties

| Improve this Doc View Source

DisjointSetBuilder

A build of IDisjointSet instances, used by the algorithm to detect potential cycles in the MST.

Declaration
public Func<int, IDisjointSet> DisjointSetBuilder { get; }
Property Value
Type Description
Func<System.Int32, IDisjointSet>
| Improve this Doc View Source

Sorter

The IInputMutatingSort algorithm to be used to sort the edges of the graph.

Declaration
public IInputMutatingSort Sorter { get; }
Property Value
Type Description
IInputMutatingSort

Methods

| Improve this Doc View Source

Find(IGraph, IGraphDistances)

Finds the Minimum Spanning Tree (MST) of the provided graph using the Kruskal'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>>
Remarks

Implements

Extension Methods