Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's and Kruskal's algorithm - Coggle Diagram
Prim's and Kruskal's algorithm
Given n points, connect them in the cheapest possible way so that there will be a path between every pair of points. It provides the cheapest way to achieve connectivity
The question can be posed as the minimum spanning tree problem
A spanning tree of an undirected connected graph is its connected
acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning
tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges. The minimum spanning tree problem is the problem of
finding a minimum spanning tree for a given weighted connected graph
Prim’s algorithm constructs a minimum spanning tree through a sequence
of expanding subtrees. The initial subtree in such a sequence consists of a single
vertex selected arbitrarily from the set V of the graph’s vertices
The algorithm stops after all the graph’s vertices have
been included in the tree being constructed
ALGORITHM
//Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
VT ← {v0} //the set of tree vertices can be initialized with any vertex
ET ← ∅
for i ← 1 to |V | − 1 do
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
such that v is in VT and u is in V − VT
VT ← VT ∪ {u∗}
ET ← ET ∪ {e∗}
return ET
After we have identified a vertex u∗ to be added to the tree, we need to perform
two operations:
For each remaining vertex u in V − VT that is connected to u∗ by a shorter
edge than the u’s current distance label, update its labels by u∗ and the weight of the edge between u∗ and u, respectively
Move u∗ from the set V − VT to the set of tree vertices VT
In particular, if a graph is represented by
its weight matrix and the priority queue is implemented as an unordered array, the algorithm’s running time will be in O(|V| ^ 2)
If a graph is represented by its adjacency lists and the priority queue is implemented as a min-heap, the running time of the algorithm is in O(|E| log |V|)
The algorithm constructs a minimum spanning tree as an expanding sequence of
subgraphs that are always acyclic but are not necessarily connected on the intermediate stages of the algorithm
The algorithm begins by sorting the graph’s edges in nondecreasing order of
their weights
Then, starting with the empty subgraph, it scans this sorted list,
adding the next edge on the list to the current subgraph if such an inclusion does not create a cycle and simply skipping the edge otherwise
ALGORITHM
//Kruskal’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = V,E
//Output: ET , the set of edges composing a minimum spanning tree of G
sort E in nondecreasing order of the edge weights w(ei1
) ≤ ... ≤ w(ei|E|
)
ET ← ∅; ecounter ← 0 //initialize the set of tree edges and its size
k ← 0 //initialize the number of processed edges
while ecounter < |V | − 1 do
k ← k + 1
if ET ∪ {eik
} is acyclic
ET ← ET ∪ {eik
}; ecounter ← ecounter + 1
return ET
A new cycle is created if and only if the new edge
connects two vertices already connected by a path, i.e., if and only if the two vertices belong to the same connected component
Each connected component of a subgraph generated by Kruskal’s algorithm is a tree
because it has no cycles
The time efficiency of Kruskal’s algorithm will be in O(|E| log |E|) when used an efficient sorting algorithm
Operations of Union-Find
makeset(x) creates a one-element set {x}. It is assumed that this operation can
be applied to each of the elements of set S only once
find(x) returns a subset containing x
union(x, y) constructs the union of the disjoint subsets Sx and Sy containing
x and y, respectively, and adds it to the collection to replace Sx and Sy, which are deleted from it
Most implementations of this abstract data type use one element from each of
the disjoint subsets in a collection as that subset’s representative
There are two principal alternatives for implementing this data structure
The second one, called the quick union, optimizes the union operation
represents each subset by a rooted tree
The first one, called the quick find, optimizes the time efficiency of the find operation
It uses an array indexed by the elements of the underlying set S; the array’s values indicate the representatives of the subsets containing those elements. Each subset is implemented as a linked list whose header contains the
pointers to the first and last elements of the list along with the number of elements in the list
A simple way to improve the overall efficiency of a sequence of union operations is to always append the shorter of the two lists to the longer one. This modification is called union by size
In fact, an even better efficiency can be obtained by combining either variety of quick union with path compression . This modification makes every node
encountered during the execution of a find operation point to the tree’s root