Package edu.princeton.cs.algs4

Class DepthFirstOrder

  • public class DepthFirstOrder
extends Object
    The DepthFirstOrder class represents a data type for determining depth-first search ordering of the vertices in a digraph or edge-weighted digraph, including preorder, postorder, and reverse postorder.

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

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • DepthFirstOrder

        public DepthFirstOrder​(Digraph G)
        Determines a depth-first order for the digraph G.
        Parameters:
        G - the digraph

      • DepthFirstOrder

        public DepthFirstOrder​(EdgeWeightedDigraph G)
        Determines a depth-first order for the edge-weighted digraph G.
        Parameters:
        G - the edge-weighted digraph

    • Method Detail

      • pre

        public int pre​(int v)
        Returns the preorder number of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the preorder number of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • post

        public int post​(int v)
        Returns the postorder number of vertex v.
        Parameters:
        v - the vertex
        Returns:
        the postorder number of vertex v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • post

        public Iterable<Integer> post()
        Returns the vertices in postorder.
        Returns:
        the vertices in postorder, as an iterable of vertices

      • pre

        public Iterable<Integer> pre()
        Returns the vertices in preorder.
        Returns:
        the vertices in preorder, as an iterable of vertices

      • reversePost

        public Iterable<Integer> reversePost()
        Returns the vertices in reverse postorder.
        Returns:
        the vertices in reverse postorder, as an iterable of vertices

      • main

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