Classical eulerian cycle algorithm: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 10: Line 10:


== Induction step ==
== Induction step ==
If the start node has
== Complexity ==
Both for directed andundirected graphs, the asymtptotic complexity is <math>\mathcal{O}(n+m)</math>, where <math>n</mah> is he number of nodes and <math>m</math> the number of edges/ars.
== Remark ==
Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it mus be hidden from the algorithm up to its termination to meet the linear complexity.

Revision as of 09:04, 12 October 2014

General information

Algorithmic problem: Eulerian cycle

Type of algorithm: recursion with an arbitrarily chosen start node as an additional input.

Induction basis

Abstract view: The output sequence [math]\displaystyle{ S }[/math] of nodes and arcs is initialized so as to contain the start node [math]\displaystyle{ s }[/math] and nothing else.

Induction step

If the start node has

Complexity

Both for directed andundirected graphs, the asymtptotic complexity is [math]\displaystyle{ \mathcal{O}(n+m) }[/math], where [math]\displaystyle{ n\lt /mah\gt is he number of nodes and \lt math\gt m }[/math] the number of edges/ars.

Remark

Of course, the edges/arcs need not be removed permanently. However, when an edge/arc is processed, it mus be hidden from the algorithm up to its termination to meet the linear complexity.