 | I'm trying to create a screen saver based on drawing eulerian circuits
(every edge used once and end up where you started) for graphs. The
degree of every vertex in my graph is even so I know it is eulerian.
My current algorithm is:
for each vertex v
random order v's neighbors in adjacency list
path = ""
v <-- random starting vertex
while (edges remain)
<--- next untried edge incident with v
remove edge from G
Perform Bredth first search on G starting from v
if (num reachable vertices from v = num vertices with degree > 0)
add to path
else
add back to G
end while
This algorithm is too slow for my needs. I'm doing a BFS after adding
each new edge to my path. This can't be right. How can I do it
better? Can I do it in O(|E|) time? Ideally I would like the
algorithm to be able to generate any eulerain tour.
Any help will be greatly appreciated.
Thanks,
Ken
|
|
