Covering trees
In order to minimize the cost of power grids, wiring connections, piping, automatic voice recognition, etc., we use algorithms that gradually build a spanning tree (or more of these trees) as intermediate steps in the process of search for minimum covering trees.
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 tree covering:
- as long as we have not added n-1 edges to G', with n the number of vertices of the graph, we choose an edge of G in such a way that its addition does not create a cycle in G'.
- as long as the number of remaining edges is greater than n-1, we remove an edge from G such 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 algorithm
At the beginning, the graph G' only contains the vertices of G and we have an empty queue (fifo) f :
- for each vertex v by G
- add v To f
- to sourt out f in ascending order
- as long as the queue is not empty
- scroll f -> edge To
- if the addition of To does not create a cycle in G' so add To in G'
- return G'
To know if we create a cycle, it suffices to know if we 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's algorithm
The principle consists in enlarging a tree by adding an edge of minimum weight incident to the tree.
At the beginning, the graph G' contains only one vertex of G:
- as long as G' does not contain all the vertices of G
- put in a queue all the edges of G which connect a vertex of G' to a vertex which is not in G'
- sort in ascending order the queue
- as long as the queue is not empty or an edge has not been added
- scroll the queue -> edge To
- if the addition of To does not create a cycle in G' then add To in G'
The algorithm being complex to understand in writing, we will show an example:
Kruskal step by step
Below is the list of edges sorted in order of weight:
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
No cycle detected
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
No cycle detected
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
No cycle detected
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
No cycle detected
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
| Fish bone | 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 detected, n-1 edge-> END
| Fish bone | ED | AB | CD | AE | BC | EF | CF | AF | BF | FD |
| Weight | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
Prim step by step
