3

I managed to create an algorithm that finds an eulerian path(if there is one) in an undirected connected graph with time complexity O(k^2 * n) where:

k: number of edges

n: number of nodes

I would like to know if there is a better algorithm, and if yes the idea behind it.

Thanks in advance! :)

Improve this question
2
  • 3
    You can get to O(k) with Hierholzer's algorithm. Commented Nov 24, 2016 at 15:52
  • Thanks for the answer :) Commented Nov 24, 2016 at 17:00

1 Answer 1

Reset to default
5

Hierholzer's algorithm runs in O(k) time: https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm

First you find a path between the two vertices with odd degree. Then as long as you have a vertex on the path with unused edges, follow unused edges from that vertex until you get back to that vertex again, and then merge in the new path.

If there are no vertices with odd degree then you can just start with an empty path at any vertex.

If the number of vertices with odd degree is not 0 or 2, then there is no Eulerian path.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Really helpful answer. Thanks a lot :)
From wiki, Hierholzer's algorithm computes Euler cycles, not Euler path. Can you give me a citation for this answer's algorithm?
It's easy to prove that it works. If you remove initial path between odd vertices, then all vertices in the remaining graph have even degree. You'll find an Eulerian cycles in every connected component of this graph and add them to the initial path.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.