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 adjacency list and implementing the priority queue as a min-heap, it's running time will go to O(|E| log |V |).

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

A collection of one-element subsets in which each of them has a different element from the set S

Optimizes time efficiency

Optimizes union operation

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, with ties broken arbitrarily

Turns the worst-case time efficiency in (n log n)

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