ALGORITHM 399. SPANNING TREE [HI.

The article presents an algorithm for spanning tree (T). This procedure grows a spanning tree T for a given undirected loop-free graph G = (N, E) of v vertices and e edges. If G is disconnected a spanning forest will be grown. If neither of the vertices is included in a tree, the edge is taken as a new tree and its vertices numbered by an incremented component number c. Finally, if both vertices are in the same tree, the edge completes a fundamental cycle of the graph with respect to the spanning tree and consequently will not be considered further. The main loop in the procedure is executed e times.