Euler circuit

[ernest]

Hello all,

I'm stuck with a problem where I need to find
an euler circuit, I know he Fleury's algo, but
I would like to know if there is enuthing better, and
besides I need an implementation. Can anyone help me?

best regards, ernesto

[Alessandro]

I took this from USACO site.

# circuit is a global array
find_euler_circuit
circuitpos = 0
find_circuit(node 1)

# nextnode and visited is a local array
# the path will be found in reverse order
find_circuit(node i)

if node i has no neighbors then
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
else
while (node i has neighbors)
pick a random neighbor node j of node i
delete_edges (node j, node i)
find_circuit (node j)
circuit(circuitpos) = node i
circuitpos = circuitpos + 1

To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it.

[Pavl0]

You can use modification of DFS

DFS( V)
{

for all E DFS(E.V)

add_to list(V);

}

it will give you list of V in euler cycle
end renember check all E only one time