Minimum_Spanning_Tree.md

Minimum Spanning Tree

Table of Contents

• Minimum Spanning Tree
• Table of Contents
• Definitions
• Union & Find - Find - Union
  • Pseudo code with Complexity
    • Arrays
    • Trees
    • Balanced Trees
• Prim's algorithm
  • Complexity
  • Pseudo code
  • Gif
• Kruskal’s algorithm
  • Complexity
  • Pseudo code
  • Gif

Definitions

• Tree : a connected acyclic graph
• Spanning Tree : a undirected graph is a subset of its edges that forms a tree connecting all vertices
• The weight of a spanning tree is the sum of the weights of its edges
• A minimal spanning tree in a graph is a spanning tree of minimal weight
• Partitions are just splitting a set into subsets.

Union & Find

The purpose of the Union & Find structure is to efficiently represent a partition.

In other words, we have a set of elements that we want to assemble in order to get groups of elements. We also want to be able to determine which element belongs in which group.

Find

Find lets us "find" out the group an element belongs to, which is represented by one of it's elements, kind of like a leader (root of a tree for example).

This is also used to "compact" the whole "branch" of a tree, so further calculations will be more efficient.

Union

This is the operation that lets us fuse two groupe together. Its purpose is also to make sure trees remain as shallow as possible (deep trees = longer computing time for most algorithms).

That is why when fusing trees with Union, the smaller tree is put under the bigger one.

Pseudo code with Complexity

Arrays

def Init(n)
  for i = 0 . . . n − 1 do
    P[i] = i
  return P

Complexity : O(n)

def Find(x,P)
  return P[x]

Complexity : O(1)

def Union(x,y,P)
  for i = 0 . . . n − 1 do
    if P[i] == P[y] then
      P[i] = P[x]

Complexity : O(n)

Trees

def Find(x,π)
  if π[x] == x then
    return x
  return Find (π[x], π)

Complexity : O(height)

def Union(x,y,π)
  idx = Find(x, π)
  idy = Find(y, π)
  π[idx] = idy

Complexity: O(height)

Balanced Trees

Init : Same as tree but with height parameter
Find : Same as Tree but Complexity: O(t log n) without compression and O(t × log∗n) with commpression
Union : Complexity change depending on the used Find function if the find do height compressionit will be O(t × log∗n)
ortherwise O(t log n)

The find can be changed to compress the height here how it's done

def Find(x,π)
  if x== π[x]
    return x
  π[x] = Find(x,π)
  return π[x]

def Union(x,y,π,h)
  idx = Find(x, π)
  idy = Find(y, π)
  if h[idx] ≤ h[idy] then
    π[idx] = idy
    if h[idx] == h[idy] then
      h[idy] + +
  else
    π[idy] = idx

Prim's algorithm

TL;DR : Select starting node and then always take the edge with the smallest weight from selected nodes

Complexity

(Same as Dijkstra's algorithm)

• O(|V|2) is we use an array for d (distance)
• O(|E| log |V|) if we use a priority queue, because of the updates

Pseudo code

def Prim(G):
  for s vertex of G do
    d[s], π[s] = +∞, ∅
  Choose a vertex s0 and set d[s0] = 0
  todo = all vertices
  T = ∅
  while todo != ∅ do
    s = Extract the element of todo that minimizes d
    if s != s0 then
      Add s − π[s] to T
    for s,w−→ t in E do
      if w < d[t] then
        d[t], π[t] = w, s
  return T

Gif

Faster gif

Longer gif with extra steps

Kruskal’s algorithm

TL;DR : Select edges in increasing weight order, as long as it doesn't create a loop

Complexity

• O(|E| log |E|) = O(|E| log |V|) for sorting (as |V| ≤ |E|²)
• O(|E| log∗|E|) for the union & find operations So the bottleneck is the sorting preprocess, costing O(|E| log |V|)

Pseudo code

def Kruskal(G):
  Sort the edges by increasing weight
  π, h = init(V)
  T = ∅
  for s − t in increasing weight order do
    if find(x,π) != find(y,π) then
      Add s − t to T
      union(x,y,π,h)
  return T

Gif