Minimum Spanning Tree Problem

Given n points, connect them in the cheapest possible way so that will be a path between every pair of points

Prim's Algorithm

A spaning tree of an undirected connected graph is its tree that contains all the vertices of the graph. If it has weights assigned to it s edges, a minimum spanning tree is its spanning tree of the smallest weight (sum of the weights on all its edges).

  • constructs a minimum spanning tree through a sequence of expanding subtrees
  • the inicial subtree consists of a single vertex selected arbitrarily
  • on each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it nearest vertex in the tree by an edge go the smallest weight
  • the algorithm stops after all the graph's vertices have been included in the tree being constructed

Can be used on weighted graphs with negative wheights and/or negative cycles

Efficiency:

  • Adjacency Matrix and no heap: Θ(|V ²|)
  • Adjacency List and Heap: Θ((|V | + |E |) log |V |)

Kruskal's Algorithm

It's a greedy algorithm that begins by sorting the graph's edges in nondecreasing order of their weights. Then, starting with the empty subgraph, it scans this sorted list, adding the next edge on the list to the current subgraph if such an inclusion does not create a cycle and simply skipping the edge otherwise

Efficiency:

  • Adjacency Matrix and no heap: Θ(|V ²|)
  • Adjacency List and Heap: Θ((|V | + |E |) log |V |)

Best for sparse graphs

Best for dense graphs

Disjoint Subsets and Union-Find Algorithms

Its an Abstract Data Type that stores a collection of disjoint (non-overlapping) sets

Subset's representative element

  • it's an element from each disjoint that will represent the subset

Quick Find

Quick Union

  • optimizes the find operation
  • optimizes the union operation
  • uses an array indexed by the elements of the underlying set S
  • the array's values indicate the representatives of the subsets containing the pointers to the first and last elements of the list along with the number of elements in the list

Efficiency:
find ∈ Θ(1)
union ∈ Θ(n)

  • represents each subset by a rooted tree - the tree's edges are directed from children to their parents
  • the nodes of the tree contain the subset's elements (one per node), with the root's element considered the subset's representative

Efficiency:
find ∈ Θ(n)
union ∈ Θ(1)

Hugo de Almeida Medeiros - ham4@cin.ufpe.br