Level Structure - Definition and Construction

Definition and Construction

Given a connected graph G=(V,E) with V the set of vertices and E the set of edges, and with a root vertex r, the level structure is a partition of the vertices into subsets L_i called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L₀ = {r}, and then, for i > 0, defining L_i to be the set of vertices that are neighbors to vertices in L_{i − 1} but are not themselves in any earlier level.

If a breadth first search of G is performed, starting from r, then the vertices in each level will be found as a consecutive subsequence of the breadth first ordering of the graph. These subsets may be computed by performing a breadth first search, calculating the level of each vertex v as it is processed by the search by adding one to the minimum level of an already-processed neighbor of v, and storing this level with v so that its later neighbors may perform the same calculation.