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
We can represent
the
points
given by
vertices
of a graph;
possible
connections
by the graph’s
edges
;
connection costs
by the
edge weights
.
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
The
minimum spanning tree problem
is the problem of finding a minimum spanning tree for a given weighted connected graph.
(Where the weight of a tree is defined as the sum of the weights on all its edges)
Prim’s algorithm
constructs a
minimum spanning tree
through a sequence of expanding subtrees.
On each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to it the nearest vertex not in that tree.
The tree generated by the algorithm is obtained as the set of edges used for the tree expansions.
its necessary to provide each vertex not in the current tree with the information about the shortest edge connecting the vertex to a tree vertex.
We can provide such information by attaching two labels to a vertex:
The name of the nearest tree vertex and The length (the weight) of the corresponding edge.
With such labels finding the next vertex becomes a
simple task of finding a vertex with the smallest distance label in the set
V − VT
Alternatively, we can split
the vertices that are not in the tree into two sets, the
fringe/candidates
(contains only the vertices that are not in the tree but are adjacent to at least one tree vertex.) and the
unseen
(are all the other vertices of the graph they are yet to be affected by the algorithm)
After we have identified a vertex u∗ to be added to the tree:
:one: Move u∗ from the set V − VT to the set of tree vertices VT .
:two: 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.
How efficient? depends on the data structures
chosen for the graph itself and for the priority queue of the set V − VT whose vertex priorities are the distances to the nearest tree vertices
running time will be in Θ(|V |
2) if a graph is represented by
its weight matrix and the priority queue is implemented as an unordered array,
O(|E| log |V |) If a graph is represented by its adjacency lists and the priority queue is implemented as a min-heap
Kruskal’s algorithm
looks at a minimum spanning tree of a weighted connected graph as an acyclic subgraph with |V | − 1 edges for which the sum of the edge weights is the smallest
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 time efficiency of Kruskal’s algorithm will be in
O(|E| log |E|).
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
On each iteration, the algorithm
takes the next edge (u, v) from the sorted list of the graph’s edges, finds the trees containing the vertices u and v, and, if these trees are not the same, unites them in a larger tree by adding the edge (u, v).
Union-Find Algorithms
:efficient algorithms for doing so, including the crucial check for whether two vertices belong to the same tree
quick find, optimizes the time efficiency of the find operation; e quick union, optimizes the union operation.