Documentation of 'edu.princeton.cs.algs4.DirectedEulerianPath' Java class
DirectedEulerianPath
Skip navigation links
edu.princeton.cs.algs4

Class DirectedEulerianPath


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

    This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.

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

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

    • Constructor Summary

      Constructors 
      Constructor and Description
      DirectedEulerianPath(Digraph G)
      Computes an Eulerian path in the specified digraph, if one exists.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method and Description
      boolean hasEulerianPath()
      Returns true if the digraph has an Eulerian path.
      static void main(java.lang.String[] args)
      Unit tests the DirectedEulerianPath data type.
      java.lang.Iterable<java.lang.Integer> path()
      Returns the sequence of vertices on an Eulerian path.

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • DirectedEulerianPath

        public DirectedEulerianPath(Digraph G)
        Computes an Eulerian path in the specified digraph, if one exists.
        Parameters:
        G - the digraph

    • Method Detail

      • path

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

      • hasEulerianPath

        public boolean hasEulerianPath()
        Returns true if the digraph has an Eulerian path.
        Returns:
        true if the digraph has an Eulerian path; false otherwise

      • main

        public static void main(java.lang.String[] args)
        Unit tests the DirectedEulerianPath data type.
        Parameters:
        args - the command-line arguments
Skip navigation links

DataMelt 3.0 © DataMelt by jWork.ORG

You see the box below because you did not login.