Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Algorithm on euler circuits

Revision en1, by hiddentesla, 2016-12-13 17:57:31

so im learning Euler circuit now, and i found this algorithm

'tour' is a stack

find_tour(u):
	for each edge e=(u,v) in E:
		remove e from E
		find_tour(v)
	prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

source: http://www.algorithmist.com/index.php/Euler_tour

i coded it, and got AC in an euler circuit problem (the problem guarantees that there is an euler circuit) however, i noticed that in the bottom of the algorithm, it says [WARNING! There is some error in this pseudo-code. The algorithm is not correct!]

does this mean that the algo has a high chance to print euler circuit? or something else?

Tags graph, eulerian path

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hiddentesla 2016-12-13 17:57:31 744 Initial revision (published)