## Class DepthFirstOrder

• Object
• edu.princeton.cs.algs4.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 Summary

Constructors
Constructor Description
`DepthFirstOrder​(Digraph G)`
Determines a depth-first order for the digraph `G`.
`DepthFirstOrder​(EdgeWeightedDigraph G)`
Determines a depth-first order for the edge-weighted digraph `G`.
• ### Method Summary

All Methods
Modifier and Type Method Description
`static void` `main​(String[] args)`
Unit tests the `DepthFirstOrder` data type.
`Iterable<Integer>` `post()`
Returns the vertices in postorder.
`int` `post​(int v)`
Returns the postorder number of vertex `v`.
`Iterable<Integer>` `pre()`
Returns the vertices in preorder.
`int` `pre​(int v)`
Returns the preorder number of vertex `v`.
`Iterable<Integer>` `reversePost()`
Returns the vertices in reverse postorder.
• ### Methods inherited from class java.lang.Object

`clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### 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