Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm and Kruskal’s algorithm - Coggle Diagram
Prim's Algorithm and Kruskal’s algorithm
Prim's Algorithm
A spanning tree of an undirected connected graph is its connected acyclic subgraph that contains all the vertices of the graph.
A minimum spanning tree is its spanning
tree of the smallest weight
Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding subtrees
It's necessary to provide each vertex not
in the current tree with the information about the shortest edge connecting the vertex to a tree vertex.
Labels
The name of the nearest tree vertex
The length (the weight) of the
corresponding edge
To add
Move u∗ from the set V − VT to the set of tree vertices VT
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
Prim’s algorithm always yield a minimum spanning tree
Efficiency
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 Theta(|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 |).
Kruskal’s 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.
With an efficient sorting algorithm, the time efficiency of Kruskal’s algorithm will be in O(|E| log |E|).
Disjoint Subsets and Union-Find Algorithms
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
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
Alternatives for implementation
Quick Find
Quick Union