Introduction Jump table is a data structure for storing a sorted list of elements with the help of a linked table hierarchy connected to a subsequence of elements. Jump table allows to handle item lookups in an efficient way. A jump table is a probabilistic data structure, which means that it skips several elements of the entire list, hence the name. We can think of a jump table as an extended version of a linked table.
Undirected rings An undirected graph with rings is shown below, where there are two rings, 0-2-1-0 and 2-3-4-2, respectively.
To detect rings in an undirected graph, you can use depth-first search. Suppose we start from vertex 0, then walk to the adjacent vertex 2, then walk to the vertex 1 adjacent to vertex 2. Since vertex 0 and vertex 1 are adjacent and vertex 0 is labeled, it means we have spared a loop, so there is a loop in the undirected graph.
Basic concepts Definition of a graph A graph is a binary consisting of a set of points V={vi}V={vi} and a set E={ek}E={ek} of unordered pairs of elements in VV, denoted G=(V,E)G=(V,E), elements vivi in VV are called vertices and elements ekek in EE are called edges.
For two points u,vu,v in VV, if the edge (u,v)(u,v) belongs to EE, then the two points u,vu,v are said to be adjacent and u,vu,v is called the endpoint of the edge (u,v)(u,v).
