Level structure
From Wikipedia, the free encyclopedia
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.[1]
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 Li called levels, consisting of the vertices at distance i from r. Equivalently, this set may be defined by setting L0 = {r}, and then, for i > 0, defining Li to be the set of vertices that are neighbors to vertices in Li − 1 but are not themselves in any earlier level.[1]
The level structure of a graph can be computed by a variant of breadth-first search:[2]: 176
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'
