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:
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“No construction stiff working overtime takes more stress and straining than we did just to stay high.”
—Gus Van Sant, U.S. screenwriter and director, and Dan Yost. Bob Hughes (Matt Dillon)