Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prims algorithm, Kruskals algorithm, if ET ∪ {eik} is acyclic, return ET,…
Prims algorithm
n points
cheapest possible way
spanning tree
undirected connected graph
acyclic subgraph
O(|E| log |V |)
Kruskals algorithm
minimum spanning tree problem
optimal solution
minimum spanning tree of a weighted connected graph G = ( V,E ) as an acyclic
subgraph with |V | − 1 edges for which the sum of the edge weights is the smallest.
ET ← ∅;
k ← 0
while ecounter < |V | − 1 do
k ← k + 1
can be proved by repeating the essential steps of the proof of prims algorithm
O(|E| log |E|).
if ET ∪ {eik} is acyclic
ET ← ET ∪ {eik}; ecounter ← ecounter + 1
return ET
disjoint subsets and union find algorithms
dynamic partition some n elements set S into a collection of disjoint subsets
quick find
quick union
VT ← {v0}
for i ← 1 to |V | − 1 do
VT ← VT ∪ {u∗}
ET ← ET ∪ {e∗}
return ET
ET ← ∅