Class DepthFirstOrder

java.lang.Object

DepthFirstOrder

public class DepthFirstOrder
extends java.lang.Object

This program computes the preorder and postorder of a digraph or edge-weighted digraph (ignoring the weights). This is a client of the following ADTs: Digraph, EdgeWeightedDigraph, DirectedEdge, Queue, and Stack.

Constructor Summary

Constructors

Constructor and Description
DepthFirstOrder(Digraph G) Constructor.
DepthFirstOrder(EdgeWeightedDigraph G)

Method Summary

Methods

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Receives, on the command-line, the name of a file containing the description of a digraph or an edge-weighted digraph (but ignores the weights of the edges).
java.lang.Iterable<java.lang.Integer>	post() Returns vertices in postorder as an Iterable.
int	post(int v) Returns the postorder number of vertex v.
java.lang.Iterable<java.lang.Integer>	pre() Returns vertices in preorder as an Iterable.
int	pre(int v) Returns the preorder number of vertex v.
java.lang.Iterable<java.lang.Integer>	reversePost()

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)

Constructor. Computes the depth-first search preorder and postorder of digraph G. The vertices are put into a queue in preorder. The vertices are put into another queue in postorder. Runs in O(E + V) time.

Implementation details: The method calls dfs(), where most of the work is done.)

DepthFirstOrder

public DepthFirstOrder(EdgeWeightedDigraph G)

Method Detail

pre

public int pre(int v)

Returns the preorder number of vertex v.

post

public int post(int v)

Returns the postorder number of vertex v.

post

public java.lang.Iterable<java.lang.Integer> post()

Returns vertices in postorder as an Iterable.

pre

public java.lang.Iterable<java.lang.Integer> pre()

Returns vertices in preorder as an Iterable.

reversePost

public java.lang.Iterable<java.lang.Integer> reversePost()

main

public static void main(java.lang.String[] args)

Receives, on the command-line, the name of a file containing the description of a digraph or an edge-weighted digraph (but ignores the weights of the edges). Prints the preorder and postorder of the verices of the digraph.

Here is the result of a sample run:

 % java DepthFirstOrder tinyDAG.txt
    v  pre post
 --------------
    0    0    8
    1    3    2
    2    9   10
    3   10    9
    4    2    0
    5    1    1
    6    4    7
    7   11   11
    8   12   12
    9    5    6
   10    8    5
   11    6    4
   12    7    3
 Preorder:  0 5 4 1 6 9 11 12 10 2 3 7 8 
 Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8 
 Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4 
 

Data files may be found in http://algs4.cs.princeton.edu/42directed/tinyDAG.txt and http://algs4.cs.princeton.edu/42directed/tinyDG.txt