Get this book -> Problems on Array: For Interviews and Competitive Programming

Cheriton-Tarjan algorithm is a modification of Kruskal's algorithm designed to reduce the `O(e log e)`

term.

Similar to Kruskal's algorithm, it grows a spanning forest, beginning with a forest of n = |G| components each consisting of a single node. Now the term `O(e log e)`

comes from selecting the minimum edge from a heap of e edges. Since, every component `Tu`

must eventually be connected to another component, this algorithm keeps a separate heap `PQu`

for each component `Tu`

, so, that initially `n`

smaller heaps are used. Initially, `PQu`

will contain only `DEG(u)`

edges, since `Tu`

consists only of vertex `u`

. When `Tu`

and `Tv`

are merged, `PQu`

and `PQv`

must also be merged. This requires a modification of the data structures, since heaps cannot be merged efficiently. This is essentially because merging heaps reduces to building a new heap.

Any data strucutre in which a minimum element can be found efficiently is called a priority queue. A heap is one form of priority queue, in which elements are stored as an array, but viewed as a binary tree. There are many other forms of priority queue. In this algorithm, `PQu`

will stand for a priority queue which can be merged.

It stores a list Tree of the edges of a minimum spanning tree. The components of the spanning forest are represented as Tu and the priority queue of edges incident on vertices of Tu is stored as `PQu`

.

### Complexity

The complexity of Cheriton-Tarjan minimum spanning tree algorithm is `O(E log(log V))`

where `E`

is the number of edges and `V`

is the number of vertices.

### Pseudocode

Consider the following pseudo-code for Cheriton-Tarjan Minimum Spanning tree algorithm:

```
MST-CHERITON-TARJAN (G = (V,E), w)
Q := null /* A Set of edges in minimum spanning tree */
for each vertex v in V[G] /* V[G] is the vertex set in graph G */
do (v belongs to Q)
stage(v) = 0
j = 1 /* j is stage number which is initialized to 1 */
while |Q| > 2 /* Number of elements in Q is greater than 2 */
do (Q belongs to T1) /* Let T1 be the tree in front of Q */
if (stage(T1) == j)
do j = j+1
CLEAN-UP
find edge (u,v) in E with minimum weight such that u belongs to T1 , v belongs to `V-T1`
let T2 be the tree in Q that contains v
T = MERGE(T1,T2) /* by adding edge (u,v) to MST*/
Q = Q-T1-T2 /* Remove T1 & T2 from Q */
stage(T) = 1 + minimum_of{ stage(T1), stage(T2) }
Q = T
END
ClEAN-UP
Shrink G to G* where G* is G with each tree shrunk to a single node and only those edges (u,v) Ă G*, u Ă T, vĂ T', that are shortest incident edges between disjoint T, T'.
```