edu.princeton.cs.algorithms

Class DepthFirstOrder

java.lang.Object

edu.princeton.cs.algorithms.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

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 java.lang.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

post

public int post(int v)

Returns the postorder number of vertex v.

Parameters:

v - the vertex

Returns:

the postorder number of vertex 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.