[prev] 28 [next]

Euler Path and Tour (cont)

Assume the existence of degree(G,v) (degree of a vertex)

Function to check whether a graph has a Euler path: 

int hasEulerPath(Graph g, Vertex v, Vertex w)
{
   int t = degree(g,v) + degree(g,w);
   if ((t % 2) != 0) return 0;
   Vertex x;
   for (x = 0; x < nV(g); x++) {
      if (x != v && x != w) {
         if ((degree(g,x) % 2) != 0)
            return 0;
      }
   }
   return 1;
}

Analysis:

  • assume that connectivity is already checked
  • assume that degree is available via O(1) lookup
  • single loop over all vertices ⇒ O(V)