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



Description

Proof

Snapshots