Sequential Computation of a Spanning Tree
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 label N) except exactly one vertex which is in an active state (encoded by label A) and that all edges have label 0. The algorithm will run in such a way that at every time exactly one vertex will be A-labelled.
