Please enable JavaScript.
Coggle requires JavaScript to display documents.
Minimum-Cost Spanning Trees - Coggle Diagram
Minimum-Cost Spanning Trees
Introduction
Given n points,
connect
them in the
cheapest possible way
so that there will be a
path between every pair
of points.
Aplications
Design of all kinds of networks
Classification purposes
COnstructing approximate solutions
Minimun-cost spanning tree (MST)
Let G be an undirected connected graph.
MST is a connected acyclic subgraph (i.e, a tree) that contains all vertices of G.
G has weights, an MST is the tree with the smallest weight (sum all weights on all edges).
Prim's Algorithm
Constructs an MST through a
sequence of expanding subtrees
.
Initial subtree consist of a
single arbitrary vertex
On each iteration, expands the current tree in a
greedy
manner by attaching to it the
nearest vertex
not in this tree.
Nearest vertex
a vertex no in the tree connected to a vertex in the tree by an edge of the smallest weight.
Algorithm stops after including all vertices
Can be used on
weighted graphs with negative
weights (and also with negative cycles)
.
Time Efficiency
Matrix with no heap is
Θ(| V |2)
.
List with heap:
Θ((| V | + | E |) log | V |)
.
Disjoint subsets (Union Find)
Kruskal
Greedy
algorithm
Initially,
n
= | V | MSTs.
On each iteration, chooses an edge of G with the smallest weight that unions two MSTs (i.e., without introducing a cycle).
Time Efficiency
Prim
best for
dense
graphs.
Kruskal
: best for
sparse
graphs.