Please can anyone help me write a program that finds an Euler cycle in a connected graph in which all vertices have even edges

Printable View

- 07-20-2005nickwokabiEuler Cycle
Please can anyone help me write a program that finds an Euler cycle in a connected graph in which all vertices have even edges

- 07-20-2005swgh
Erm, either read a book on graphics programming or do a google for it

- 07-20-2005Rashakil Fol
Graphics programming? What do Euler cycles have to do with graphics programming?

Generally speaking Nick, the human algorithm for finding Euler cyles is the following:

1. Find a cycle from node X.

2. From any node on your cycle (any node that has free edges), find a cycle from that node that only uses edges that are not yet part of your cycle. Then connect the two cycles into one.

3. Go to step 1, unless there are no edges left.

So now you still need to find an algorithm for finding a cycle in a graph.

This algorithm should work for undirected graphs; I don't know about the directed kind. Finding a cycle in a graph can be done with a variation of depth-first search.