kruskal's algorithm
could be seen as an alternative to prim's algorithm as they generally serve the same goal.
kruskals algorithm finds an mst in a graph.
initial (inefficient) proposed algorithm:
:
first we need to have an efficient way to lookup the minimal edge in
, this can be done by sorting the edges of the graph in an ascending order of weights and takes 
time.
second, we need an efficient method to check whether an edge connects two connected components, this is complicated, to solve this we introduce the union/find algorithm
the
algorithm maintains a collection of disjoint sets over some universe with the following operations:
MakeSet(x): create the set
Union(x,y): replace the set
is in which we'll call 
and the set 
is in which we'll call 
, with the single set 
Find(x): return the set containing
in the solution we propose here we use the arrays:
Set: Set[i],
, stores the set that 
belongs to
Size: Size[i] stores the size of the set
Elts: Elts[i] stores a pointer to a linked list containing the items of the set
kruskals algorithm finds an mst in a graph.
initial (inefficient) proposed algorithm:
correctness of kruskal:
at each step during the execution of, the forest 
is a subgraph of an mst of the input graph.
we need to improve 2 things to write a faster algorithm than at each step during the execution of
, the forest is a subgraph of an mst of the input graph.
the lemma represents a loop invariant that is true at the start of each iteration of the for loop. we prove the lemma by induction on the loop index.
base: before the first non-empty iteration of the loop, would contain all the vertices of 
, but no edges, and so the claim's correctness follows by the definition of an mst as a subgraph that contains all the vertices of the graph.
induction hypothesis: we assume that after the addition of
edges, the graph 
is a subgraph of an mst of , 
.
induction step: in an iteration that doesnt add an edge to, the correctness of the claim follows trivially from the induction hypothesis.
let
be the next edge that gets added to , we consider the following cases:
case 1:
, the claim follows trivially.
case 2:
, in this case, we will find that there exists another mst of , 
, such that 
. if we were to consider the graph received by adding the edge 
to the spanning tree 
, according to lem-spantree-2, in this graph theres a cycle 
. let 
be an edge in that is in but not in (theres always such an edge because otherwise 
would have a cycle and wouldnt have been picked by the algorithm). consider 
, according to lem-spantree-2, 
is a spanning tree of . at the start of the 
-th iteration, and 
wouldnt belong to 
. at this point, the algorithm had chosen to add the edge to before it tried to add , which would mean that 
, which in turn wuold mean 
, but, on the other side, is a spanning tree of , and so 
, which means 
and 
, which means is an additional mst of .
the correctness of follows from the induction assumption for 
base: before the first non-empty iteration of the loop,
would contain all the vertices of , but no edges, and so the claim's correctness follows by the definition of an mst as a subgraph that contains all the vertices of the graph.
induction hypothesis: we assume that after the addition of
edges, the graph is a subgraph of an mst of , .
induction step: in an iteration that doesnt add an edge to
, the correctness of the claim follows trivially from the induction hypothesis.
let
be the next edge that gets added to , we consider the following cases:
case 1:
, the claim follows trivially.
case 2:
, in this case, we will find that there exists another mst of , , such that . if we were to consider the graph received by adding the edge to the spanning tree , according to lem-spantree-2, in this graph theres a cycle . let be an edge in that is in but not in (theres always such an edge because otherwise would have a cycle and wouldnt have been picked by the algorithm). consider , according to lem-spantree-2, is a spanning tree of . at the start of the -th iteration, and wouldnt belong to . at this point, the algorithm had chosen to add the edge to before it tried to add , which would mean that , which in turn wuold mean , but, on the other side, is a spanning tree of , and so , which means and , which means is an additional mst of .
the correctness of
follows from the induction assumption for :
first we need to have an efficient way to lookup the minimal edge in
, this can be done by sorting the edges of the graph in an ascending order of weights and takes time.
second, we need an efficient method to check whether an edge connects two connected components, this is complicated, to solve this we introduce the union/find algorithm
the
algorithm maintains a collection of disjoint sets over some universe with the following operations:
MakeSet(x): create the set
Union(x,y): replace the set
is in which we'll call and the set is in which we'll call , with the single set
Find(x): return the set containing
in the solution we propose here we use the arrays:
Set: Set[i],
, stores the set that belongs to
Size: Size[i] stores the size of the set
Elts: Elts[i] stores a pointer to a linked list containing the items of the set
the time complexity of 
is equal to the number of items in the smaller set of the two
is equal to the number of items in the smaller set of the twoevery element is moved from a set to another 
times at most
times at mosttime complexity of \(n-1\) operations of \(\textsc{Union}\):
the usage of
is a process in which 
sets are unionised into a single set using 
calls to . this takes 
time. there are however more efficient implementations of that can achieve better performance.
we reimplement kruskal's algorithm with the help of the usage of
is a process in which sets are unionised into a single set using calls to . this takes time. there are however more efficient implementations of that can achieve better performance.
is a communication network is called secure if it has a single path between every two vertices.
given a list of pairs of numbers (vertices), connect them together until the network isnt secure anymore, then stop and output a proper message.
example: given (1,2),(2,3),(2,5),(1,6),(2,7),(7,6),(2,4).
at (7,6) the network becomes not "secure" so we stop and output a message
given a list of pairs of numbers (vertices), connect them together until the network isnt secure anymore, then stop and output a proper message.
example: given (1,2),(2,3),(2,5),(1,6),(2,7),(7,6),(2,4).
at (7,6) the network becomes not "secure" so we stop and output a message
we make use of union/find
being equal to 
means both 
are already a part of a connected component
being equal to means both are already a part of a connected component