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