1. ALGORITHM 399. SPANNING TREE [HI.
- Author
-
Seppanen, Jouko J.
- Subjects
- *
ALGORITHMS , *TREES , *GRAPHIC methods , *MATHEMATICAL variables , *ALGEBRA , *MATHEMATICAL analysis - Abstract
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.
- Published
- 1970
- Full Text
- View/download PDF