edu.princeton.cs.algs4

## 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. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the preorder, postorder, and reverse postorder operation takes take time proportional to V.

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 and 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

Methods
Modifier and Type Method and 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 Object

`clone, equals, finalize, 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