Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's algorithm and Kruskal's algorithm, Disjoint sets and Union…
Prim's algorithm and Kruskal's algorithm
Prim's algorithm
Used for the minimum spanning tree problem
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
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
Constructs a minimum spanning tree through a sequence of expanding subtrees
Always yields a minimum spanning tree
Using weight matrix and implementing the priority queue as a unordered array, it's running time will be
quadratic
Using adjacency list and implementing the priority queue as a min-heap, it's running time will go to
O(|E| log |V |)
.
Kruskal's algorithm
Used for the minimum spanning tree problem
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.
The time efficiency of Kruskal’s algorithm will be in
O(|E| log |E|)
Require a dynamic partition of some n element set S into a collection of disjoint subsets S1, S2, . . . , Sk
Disjoint sets and Union-find algorithms
Disjoint sets
A collection of one-element subsets in which each of them has a different element from the set S
Alternatives for implementing Disjoint sets
Quick Find
Optimizes time efficiency
The quick find 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
MakeSet
and
Find
have constant time efficiency, but have the
Union
is in quadratic
Union by size
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, with ties broken arbitrarily
Turns the worst-case time efficiency in (n log n)
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
Quick Union
Optimizes union operation
Represents each subset by a
rooted tree
The nodes of the tree contain the subset’s elements (one per node), with the root’s element considered the subset’s representative; the tree’s edges are directed from children to their parents
MakeSet and Union have constant time efficiency, but Find is linear