Euler Cycle  Output  

Given an alphabet of size $k$, the de Bruijn graph of order $n$ is the directed graph $G(n,k) = (V,E)$ where $V$ is the set of all $k$ary strings of length $n$ and there is a directed edge $e=(u,v)$ from $u = u_1u_2\cdots u_n$ to $v=v_1v_2\cdots v_n$ if $u_2\cdots u_n = v_1\cdots v_{n1}$. Each edge $e$ is labeled by $v_n$. Outputting the edge labels in a Hamilton cycle of $G(n,k)$ produces a DB sequence. Below (left) is a Hamilton cycle in the de Bruijn graph $G(3,2)$. Starting from 000, its corresponding DB sequence is 10111000.
Each de Bruijn graph is connected and the indegree and the outdegree of each vertex is $k$; the graph $G(n,k)$ is Eulerian. $G(n,k)$ is the line graph of $G(n{}1,k)$ which means an Euler cycle in $G(n{}1,k)$ corresponds to a Hamilton cycle in $G(n,k)$. Thus, the sequence of edge labels visited in an Euler cycle is a DB sequence. Illustrated above (right) is an Euler cycle in $G(3,2)$. The corresponding DB sequence is 0111101011001000.
Finding an Euler cycle in an Eulerian graph is lineartime solvable with respect to the size of the graph. Such an algorithm is given below. However, since the graph must be stored, applying such an algorithm to find a DB sequence requires exponential $O(k^n)$ space. As noted below, the following Euler cycle algorithm can be related to the greedy constructions.
The following algorithm for finding an Euler cycle is based on Fleury [Fle83] with details taken from [Rus03]. The basic idea is do not burn bridges. In other words, do not visit (and use up) an edge if it leaves the remaining graph disconnected.
A second wellknown Euler cycle algorithm is from Hierholzer [Hie73]:
This cyclejoining approach is the basis for all the binary shift rule constructions.
Preference tables [Alh12] (also called lookup tables [Xie87]) generalize the notion of the greedy constructions. In particular, a preference table specifies the precise order that the edges are visited for each vertex when performing Step 3 in Fleury's Euler cycle algorithm. Thus given a preference table and a root vertex, Step 3 in the algorithm can be applied to construct a DB sequence if combining the last edge from each nonroot vertex forms a spanning intree to the root. For example, the preference tables and corresponding spanning intrees for the Preferlargest, Prefersame, and Preferopposite constructions are given below for $G(3,2)$. For the Preferlargest, the only valid root is 000. For the Prefersame, either 010 or 101 could be chosen as root. The Preferopposite has a small nuance. By its strict definition, the edges will not create a spanning intree for any root. But by changing the preference for the single string 111, a spanning intree is created when rooted at 000.