# What is the right data structure for MST in a stream

In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:

H ← ∅
for each (u,v) in the stream
H ← (u, v)
if H includes a cycle
remove largest weight edge in the cycle


To make this fast we need a data structure that allows you to check if (u,v) makes a cycle and also allows you to remove the largest weight edge from a cycle.

What is a suitable data structure for this?

## 1 Answer

By noticing that $$H$$ remains a tree except when $$H \gets H \cup (a,b)$$ happens, you can use a ST-Tree, which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $$a$$ to $$b$$"

Instead of adding $$(a,b)$$ directly to $$H$$ first you check if $$a$$ and $$b$$ are connected (using the ST-Tree or a Union-Find). If they are not, you add it as possible. Otherwise, if its weight is smaller than $$max( a \to b)$$, you replace with $$(a,b)$$ the max. weight edge.