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.
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.
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
- 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.
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: