In the mathematical subfield of graph theory a level structure of a rooted graph is a partition of the vertices into subsets that have the same distance from a given root vertex.
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<sub>i</sub> called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L<sub>0</sub> = {r}, and then, for i > 0, defining L<sub>i</sub> to be the set of vertices that are neighbors to vertices in L<sub>i − 1</sub> but are not themselves in any earlier level.
The level structure of a graph can be computed by a variant of breadth-first search:
algorithm level-BFS(G, r): Q â {r} for â from 0 to âÂÂ: process(Q, âÂÂ) // the set Q holds all vertices at level â mark all vertices in Q as discovered Q' â {} for u in Q: for each edge (u, v): if v is not yet marked: add v to Q' if Q' is empty: return Q â Q'
In a level structure, each edge of G either has both of its endpoints within the same level, or its two endpoints are in consecutive levels.
The partition of a graph into its level structure may be used as a heuristic for graph layout problems such as graph bandwidth. The CuthillâÂÂMcKee algorithm is a refinement of this idea, based on an additional sorting step within each level.
Level structures are also used in algorithms for sparse matrices, and for constructing separators of planar graphs.