Hi, Here is Data Structures and Algorithms. We will introduce Chapter-7, Minimum Support Tree(MST).
MST is a sub-graph for a graph
MST is a tree sub-graph, in another word, consists of N nodes and N-1 edges.
All nodes are connected. And summation of edges' weight of MST
in minimum among all tree sub-graphs.
We will introduce Prim Algorithm first.
Prim Algorithm runs similar to Dijkstra Algorithm.
First, We choose one node from graph, and add this node into MST.
Then, We split nodes of the graph into
two sets, labelled set and unlabelled set.
We choose edge with minimum weight
among edges between the two sets.
And add this edge,
including connected node of the edge, into MST.
After such operation,
distance between the two sets may be changed.
Then we do the same with two modified sets.
We find minimum weight edge in
edges between two sets. We do this greedy algorithm again and again,
until all nodes have been added into MST.
With N-1 edges.
Now we proof correctness of Prim Algorithm
That is, to proof greedy properties.
Consider the Prim Algorithm.
Assume T is a constructing tree
with unlabelled nodes and edges
We assume there is an edge E
with minimum weight among
edges connect nodes between two sets
Obviously, there will exist
a MST of G.
There exists a MST which includes T
And includes
edge E
in it.
We proof this by contradiction
We assume
Any MST of G including T doesn't including E
We assume there is a MST T'
Because T' is connected
it must have one node belongs to labelled set of T
Assume it is Vp
And there is a node Vq belongs to unlabelled set.
There is a edge E' between
Vp and Vq, connect two sets.
This is true because T' is connected.
There is a path in labelled set from Vx to Vp
and a path in unlabelled set from Vy to Vq
We add E into T' and delete
Edge E', We get a new tree T''
Weight of T'' is no more than
Weight of T'. Because differences
between T' and T'' is that
E replace E'. And as we know, among all edges connecting two sets,
E has the minimal weight. Such that weight of T'' is no more than T'
Then We proved that T'' is a MST
with edge E.
This is contradiction with our assumption.
We proved the conclusion.
Greedy part of Prim Algorithm is correct.
That is, Every time Prim Algorithm choose minimal edge
among all edges between two sets
is correct. It will get a MST.
Let's see an example of Prim Algorithm.
First, we initialize Mark Array
to mark every node unlabelled
And set dist array for distance between source and nodes to infinite
prev of all nodes is source S.
We set dist of S to 0
Because S can get to S without any distance
And mark S as labelled.
Because MST has N nodes and N-1 edges.
We added node S into MST
We need N-1 loops for next N-1 nodes.
First, We find a node V
initially, V is S
After choose V,
We refresh dist of nodes near V
After adding V
we scan all neighbours of V
if weight between V and its neighbours are smaller
than dist of neighbours, we update the dist to
weight between V and neighbours. And set Prev as V
As V induces its neighbours
We find minimum in dist array, and call it V
If V is -1
There is no possible nodes
even if we didn't finish all N-1 loops.
This shows that we cannot find a MST
because the graph is not connected
We need to return error code.
If we find a node V, we mark V as labelled
add V and connected edge between V and labelled set into MST
and continue our next loop.
Let's look at our finding minimum in dist function.
We use -1 for infinite
this is our initial distance
We scan dist
if a node i is unlabelled and
dist of the node is smaller than MinDist
We modify MinDist to dist[i]
And mark i as V.
After finishing the loop. we find a node
with minimum dist, the node V
If V=-1 after the loop, the graph may be not connected
Time complexity of Prim is similar to Dijkstra
The algorithm runs similar as Dijkstra
Because dist need not accumulation, Prim is simpler than Dijkstra
Compare elements in dist array
and find minimum element
consume O(n^2) time. Because we need to scan dist N times
each time with O(N) time
This is proper for dense graph. If graph is sparse
we can use heap to get minimum in dist array.
Let's look at another algorithm - Kruskal Algorithm
Prim algorithm start from source
and add neighbours one by one
In contrast, Kruskal Algorithm starts from edge.
All node is in MST initially
Kruskal Algorithm consider edges.
Choose edge with minimum weight and get it into MST, then consider next,
the second minimum weight edge. We do this again and again.
During this procedure, we need to consider whether two nodes
of an edge is in same connected component.
If they are in, the edge will construct a circle
we need to ignore such edges.
until we find N-1 edges, we get a MST.
Here is an example
7 nodes stands for 7 connected components
We choose minimum weight edge and connect two connected components as one
When we consider edge V3-V6
we noticed that V3 and V6 are connected
If we add this edge, there will be a loop. So we ignore this edge
And continue this procedure until we find N-1 edges.
Let's look at Kruskal Algorithm.
First we insert all edges into
a minimum heap.
We can find the minimum with the heap conveniently
We use a variant stands for number of connected components.
At beginning, it is same as number of nodes
If this number is more than 1
Which stands for
there is not a tree because not connected
We need to continue our algorithms
until this number gets to 1.
If the heap is empty and the number of connected components is more than 1
The graph is not connected.
Stop this function and show there is no MST. otherwise
We get a minimum weight edge from the heap.
check whether two nodes of this edge are connected
If not, we choose this edge
and combine two components
Add this edge into MST
The nodes are in MST initially
So we do nothing with nodes
Number of connected components decrease by 1
We continue this loop until
Number of connected components is 1
We then find a MST
Let's look at an example. We add all edges into a heap
choose the minimum weight edge out
combine connected components
When we consider edge B-C
Because B and C are in same connected component, we cannot merge them
If we add B-C into the MST, there will be a loop
A-B-C-A. And it is not a MST
We ignore edge B-C, and continue
Finally we find 6 edge
the 6 red edges represents for
MST
Kruskal Algorithm use Union-Find structure to
maintain connected components.
In Kruscal procedure, we choose minimum weight edge each time
In worst case, all edge will be chosen from the heap
Time complexity is same as heap-sort
That is O(e*loge)
Normally, we need a little more than N times of finding
Only a few times of finding can finish this algorithm.
On average, time complexity of Kruskal is near O(N*loge)
Think over following questions.
First, there may be more than one MST of a graph
How can we design an algorithms
to get all MST of a graph. And if all edges of a graph have different weights with each other
can we get more than one MST? Obviously no. Explain Why.
Thank you