# Indian Computing Olympiad

Training Material

## Advanced graph algorithms

### Spanning trees

Let G = (V,E) be a connected, undirected, weighted graph. Our aim is to find a tree that "touches" all the vertices, using a subset of the edges of the original graph. This is called a spanning tree.

A graph could have more than one spanning tree. If the edges have weights (costs), the aim is to find a spanning tree for which the sum of the weights is minimum. This is called a minimum cost spanning tree.

```         G            Tree 1        Tree 2        Tree 3    ...

o               o             o             o
7 / \ 8         7 /           7 /               \ 8
/ 6 \           /             / 6             6 \
o-----o         o     o       o-----o       o-----o   ...
\   /           \   /             /         \
2 \ / 5         2 \ / 5           / 5       2 \
o               o             o             o

Cost = 14    Cost = 18     Cost = 16
```

How do we find the minimum cost spanning tree? There are two standard algorithms.