1
$\begingroup$

I can't come up with an eficcient way to, given a graph, find a path that crosses all edges, only once per each edge, and end in the same vertex that it started.

Can anyone point me in the right direction? I've been looking to do it using strongly-connected components (SCC), but even in a SCC, I can't guarantee, that I can cross all edges, and only once per each one. I can't remember, but I think there is a "standard" algorithm, that finds a path that crosses all edges once.

  • 0
    @Aryabhata: Sure, just went to check whether there was a preëxisting duplicate before starting to type a long answer. But your links will do just as well, I think.2012-02-26

1 Answers 1

5

Seems like you are looking for an Euler Circuit, which has standard algorithms. For instance, see Hierholzer's algorithm.