Minimum Spanning Trees

Prim's Algorithm

GraphIdx.prim_mst_edges — Function.

prim_mst_edges(n, weights, [root = 1])

Prim's algorithm for minimum spanning tree. Start from node root (will become the root node of the spanning tree). Return the parent vector and a Boolean vector indicating for each edge whether the edge is part of the spanning tree.

source

The runtime is $\mathcal{O}(|E| \log |V|)$ whereby $|E|$ are the number of edges and $|V|$ the number of nodes. We use an ordinary binary heap as priority queue:

GraphIdx.Utils.Heap — Module.

PriorityQueue datastructure (based on a implicit binary heap). Code copied from DataStructures.jl (long time ago)

source

Base.setindex! — Method.

Change the priority of an existing element, or equeue it if it isn't present.

source

Kruskal's Algorithm

GraphIdx.kruskal_mst — Function.

kruskal_mst(n, edges, weight)

Kruskal's minimum spanning tree algorithm. Return a vector indicating for each edge whether it is part of the spanning tree.

source

As you know, Kruskal's algorithm is best implemented using the UnionFind data structure which is useful on its own:

GraphIdx.Utils.UnionFind — Type.

UnionFind(n)

Classical Union-Find data structure with path compression as described e.g. in CLRS in Chapter 21 "Disjooint Sets" (3rd edition).

Example

julia> import GraphIdx.Utils: UnionFind, find, unite!

julia> u = UnionFind(2);

julia> find(u, 1) == find(u, 2)
false

julia> unite!(u, find(u, 1), find(u, 2));

julia> find(u, 1) == find(u, 2)
true

source

To make sure that we cannot unite elements before we found its representative we introduce

GraphIdx.Utils.Rep — Type.

Representant of a partition in UnionFind.

source