[prev] 94 [next]

Euler Path and Circuit (cont)

Analysis of hasEulerPath algorithm:
  • assume that connectivity is already checked
  • assume that degree is available via O(1) lookup
  • single loop over all vertices ⇒ O(V)
If degree requires iteration over vertices
  • cost to compute degree of a single vertex is O(V)
  • overall cost is O(V2)
⇒ problem tractable, even for large graphs   (unlike Hamiltonian path problem)

For the keen: Linear-time (in the number of edges, E) algorithm to compute an Euler path described in [Sedgewick] Ch.17.7