Sequential Computation of a Spanning Tree
Description:
We consider here the problem of building a spanning tree in a graph
using the depth-first search algorithm.
Suppose that all the vertices are initially in some neutral state (encoded
by the label
N) except exactly one vertex which is in an active state
(encoded by the label
A) and that all edges have the label
0.
The algorithm will run in such a way that at every time exactly one vertex
will be
A-labelled.
At each step of the computation, the
A-labelled vertex, say
u, will act as follows:
- If u has a N-labelled neighbour v, then u will activate
this neighbour: u becomes marked (with label M), v active (with
label A) and the edge {u,v} becomes 1-labelled.
- If u has no N-labelled neighbour and has a (unique) M-labelled
neighbour w then u will reactivate this neighbour: u enters a final
state (with label F) and w becomes A-labelled.
The computation stops as soon as none of the above computation rules may be applied
(in that case, all the neighbours of the
A-labelled vertex are
F-labelled).
The spanning tree is then given by the set of all
1-labelled edges.