Please enable JavaScript.
Coggle requires JavaScript to display documents.
Minimum-cost spanning tress - Coggle Diagram
Minimum-cost spanning tress
Given n points, connect them in the
cheapest possible way
so that there will be a
path between every pair
of points
Let G be an undirected connected graph, an
MST
is a
connected acyclic subgraph
(i.e, a tree) that contains all vertices of G. If
G has weights
, an
MST
is
the tree with the smallest weight
(sum of all weights on all its edges).
Prim’s algorithm
Constructs an MST through a
sequence of expanding subtrees
Initial subtree consists 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 (same as of Dijkstra’s)
Matrix with no heap: Θ(| V |²)
List with heap: Θ((| V | + | E |) log | V |)
Algorithm: void Prim(Graph G, int[] D, int[] V)
for
i ← 0
to
n(G) − 1
do
----D[i] ← ∞ ; V[i] ← −;
----setMark(G, i, UNVISITED);
H[1] ← (0, 0, 0); D[0] ← 0;
for
i ← 0
to
n(G) − 1
do
----
repeat
--------(p, v) ← removemin(H);
--------
if
v = NULL
then return
;
----
until
getMark(G, v) = UNVISITED;
----setMark(G, v, VISITED) ; V[v] ← p;
----w ← first(G, v);
----
while
w < n(G)
do
--------
if
getMark(G, w) != VISITED ∧ D[w] > weight(G, v, w)
then
------------D[w] ← weight(G, v, w);
------------insert(H, (v, w, D[w]));
--------w ← next(G, v, w);
Disjoint subsets
Operations (DS = disjoint subset):
int find(DS ds, int x);
void union(DS ds, int x, int y);
ds ← create disjointSubset(6); // {1}, {2}, {3}, {4}, {5}, {6}
union(ds, 1, 4) ; union(ds, 4, 5) ; union(ds, 1, 2);
union(ds, 3, 6); // {1, 4, 5, 2}, {3, 6}
if
find(ds, 1) = find(ds, 5)
then
print(true);
else
print(false);
Important:
subset’s
representative
element
Implementations:
quick-find
and
quick-union
Quick-find
Implementation based on quick-find
Array:
representative element for each subset elements
Each subset implement as a
linked list
Operations
create disjointSubset(n)
Initialise n linked lists
Each element is its representative
find ∈ Θ(1)
union ∈ Θ(n)
Concatenate the corresponding lists
Update all representatives
Optimisation (
union by size
): append shortest list to the largest one
Algorithm: int find(DS ds, int curr)
return ds.R[curr];
Algorithm: void union(DS ds, int a, int b)
root1, root2 ← find(ds, a), find(ds, b);
if
root1 != root2
then
----l1, l2 ← ds.sets[root1], ds.sets[root2];
----
if
l1.size < l2.size
then
swap(l1, l2);
----temp ← l2.first;
----
while
temp != NULL
do
--------ds.R[temp.element] ← l1.first.element;
--------temp ← temp.next;
----l1.last.next ← l2.first ; l1.last ← l2.last;
----l1.size, l2.size ← (l1.size + l2.size), 0;
----l2.first ← l2.last ← NULL;
Quick-union
Implementation based on quick-union
Using a parent pointer tree: root is the representative element
Operations
create disjointSubset(n)
Initialise n unitary trees
Each element is its representative
find ∈ Θ(n)
Traverse from x to the subtree’s root
union ∈ Θ(1)
Root of x points to root of y
Optimisation (
union by size/rank
): link smallest tree to the largest one
Size: number of nodes
Rank: subtree height
Algorithm: int find(DS ds, int curr)
if
ds.A[curr] = NULL
then return
curr;
ds.A[curr] ← find(ds, ds.A[curr]);
return
ds.A[curr];
Algorithm: void union(DS ds, int a, int b)
root1 ← find(ds, a);
root2 ← find(ds, b);
if
root1 != root2
then
ds.A[root2] ← root1;
Kruskal’s algorithm
Another
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: similar to Prim’s
Prim:
best for
dense
graphs
Kruskal:
best for
sparse
graphs
Algorithm: void Kruskal(Graph G, Graph G’)
edgecnt ← 1;
for
i ← 0
to
n(G) − 1
do
----w ← first(G, i);
----
while
w < n(G)
do
--------H[edgecnt++] ← (i, w, weight(G, i, w));
--------w ← next(G, i, w);
HeapBottomUp(H);
ds ← create disjointSubset(n(G));
numMST ← n(G);
while
numMST > 1
do
----(v, u, wt) ← removemin(H);
----
if
find(ds, v) != find(ds, u)
then
--------union(ds, v, u);
--------setEdge(G', v, u, wt);
--------numMST--;