public class DepthFirstOrder extends Object
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.
| 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.
|
| 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.
|
public DepthFirstOrder(Digraph G)
G - the digraphpublic DepthFirstOrder(EdgeWeightedDigraph G)
G - the edge-weighted digraphpublic int pre(int v)
v - the vertexpublic int post(int v)
v - the vertexpublic Iterable<Integer> post()
public Iterable<Integer> pre()
public Iterable<Integer> reversePost()
public static void main(String[] args)
Copyright © 2014. All Rights Reserved.