Spanning tree

A subgraph of G is a spanning graph if it has all G’s vertices.
A spanning subgraph is not necessarily connected. A spanning tree of G is a spanning subgraph of G, and this subgraph is a tree.

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.

arbre9

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.

This is called a minimal spanning tree. This problem is: there are n vertices to connect, we know the costs to connect one vertex to another, we try to connect all places at the lowest cost.

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
  • 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’
  • 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.

kruskal

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’

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

prim

Step by step Kruskal

kruskal1

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

______________

kruskal2

No cycle

Edge ED AB CD AE BC EF CF AF BF FD
Weight 2 3 4 4 5 5 6 7 8 8

______________

kruskal3

No cycle

Edge ED AB CD AE BC EF CF AF BF FD
Weight 2 3 4 4 5 5 6 7 8 8

______________

kruskal4

No cycle

Edge ED AB CD AE BC EF CF AF BF FD
Weight 2 3 4 4 5 5 6 7 8 8

______________

kruskal5

No cycle

Edge ED AB CD AE BC EF CF AF BF FD
Weight 2 3 4 4 5 5 6 7 8 8

______________

kruskal6

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

Step by step Prim

prim1prim2prim3prim4prim5prim6

Publicités