Class DepthFirstIterator

  • All Implemented Interfaces:
    GraphIterator
    Direct Known Subclasses:
    DirectedDepthFirstIterator

    public class DepthFirstIterator
    extends BreadthFirstIterator
    Iterates over the nodes of a graph in a Depth First Search pattern starting from a specified node. The following illustrates the iteration order.



    The iteration operates by maintaning a node queue of active nodes. An active node is a node that will returned at a later stage of the i teration. The node queue for a Depth First iteration is implemented as a Last In First Out queue (a Stack). A node is placed in the the node queue if it has not been visited, and it is adjacent to a a node that has been visited. The node queue intially contains only the source node of the traversal.
    Author:
    Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
    • Constructor Detail

      • DepthFirstIterator

        public DepthFirstIterator()
    • Method Detail

      • buildQueue

        protected Queue<Graphable> buildQueue​(Graph graph)
        Builds the node queue for the Iteration.
        Overrides:
        buildQueue in class BreadthFirstIterator
        Parameters:
        graph - The graph of the iteration.
        Returns:
        A Last In First Out queue (Stack)