thumb|upright=1.3|An example for an undirected Graph with a vertex and its corresponding level structure
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.
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<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.
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'
Properties
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.
Level structures are also used in algorithms for sparse matrices, and for constructing separators of planar graphs.