Package algs41

Class EulerianCycle

java.lang.Object
algs41.EulerianCycle
public class EulerianCycle extends Object
The EulerianCycle class represents a data type for finding an Eulerian cycle or path in a graph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the graph exactly once.

This implementation uses a nonrecursive depth-first search. The constructor takes Θ(E + V) time in the worst case, where E is the number of edges and V is the number of vertices Each instance method takes Θ(1) time. It uses Θ(E + V) extra space in the worst case (not including the graph).

To compute Eulerian paths in graphs, see EulerianPath. To compute Eulerian cycles and paths in digraphs, see DirectedEulerianCycle and DirectedEulerianPath.

For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne, Nate Liu

  • Field Details

  • Constructor Details

    • EulerianCycle

      public EulerianCycle(Graph G)
      Computes an Eulerian cycle in the specified graph, if one exists.
      Parameters:
      G - the graph

  • Method Details

    • cycle

      public Iterable<Integer> cycle()
      Returns the sequence of vertices on an Eulerian cycle.
      Returns:
      the sequence of vertices on an Eulerian cycle; null if no such cycle

    • hasEulerianCycle

      public boolean hasEulerianCycle()
      Returns true if the graph has an Eulerian cycle.
      Returns:
      true if the graph has an Eulerian cycle; false otherwise

    • nonIsolatedVertex

      private static int nonIsolatedVertex(Graph G)

    • satisfiesNecessaryAndSufficientConditions

      private static boolean satisfiesNecessaryAndSufficientConditions(Graph G)
      The code below is solely for testing correctness of the data type.

    • certifySolution

      private boolean certifySolution(Graph G)

    • unitTest

      private static void unitTest(Graph G, String description)

    • main

      public static void main(String[] args)
      Unit tests the EulerianCycle data type.
      Parameters:
      args - the command-line arguments