In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., we use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree.

The Internet and many other telecommunications networks have transmission links that connect nodes together in a mesh topology that includes some loops. In order to avoid bridge loops and routing loops, many routing protocols designed for such networks require each router to remember a spanning tree.

It is easy to build a spanning tree:

- as long as we do not add n-1 edges to G’, with n the number of vertices of the graph, we choose an edge of G so that its addition does not create a cycle in G’.
- as long as the number of remaining edges is greater than n-1, an edge of G is removed so that G is always connected.

The problem of spanning trees is widely used in the context of weighted edges.

To make a spanning tree of minimal weight, we will state two greedy algorithms.

## Kruskal

At first, the graph G’ contains only the vertices of G and we have an empty queue (fifo) f:

**for each vertex v**of G- add
**v**to**f**

- add
- order
**f**esc - while the queue is not empty
- unstack
**f**-> edge**a** - if
**a**does not create a cycle in graph G’ then**a**in G’

- unstack
- return G’

To know if one creates a cycle, it is enough to know if one can reach a vertex of the edge starting from the other vertex in G’. As a reminder, in a tree there is only one path from one vertex to another.

## Prim

The principle is to enlarge a tree by adding an edge of minimum incident weight to the tree.

At first, the graph G’ contains only one vertex of G:

- while G’ has not all the vertices of G
- stack in a queue all the edge of G which connects a vertex of G’ to one not in G’
- order esc the queue
- while the queue is non-empty or one has added an edge
- unstack queue -> edge
**a** - if
**a**does not create a cycle in G’ then add**a**in G’

- unstack queue -> edge

The algorithm is complex to understand in writing, we will show an example:

## Step by step Kruskal

The list of edges in order of their weights or sizes would be as follows:

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

No cycle

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

______________

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |

- Cycle detected: do not use BC

No cycle, n-1 edge -> END

Edge | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |

Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |