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 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.
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.
Read more about this topic: Level Structure
Famous quotes containing the words definition and/or construction:
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“There’s no art
To find the mind’s construction in the face:
He was a gentleman on whom I built
An absolute trust.”
—William Shakespeare (1564–1616)