Class TraversalFromRoots<V>

  • Type Parameters:
    V - vertex type
    All Implemented Interfaces:
    GraphTraversal<V>
    Direct Known Subclasses:
    BFS, DFS

    public abstract class TraversalFromRoots<V>
    extends Object
    implements GraphTraversal<V>
    A graph traversal is the problem of visiting all the nodes in a graph in a particular manner. For a directed graph, this implementation chooses as roots those vertices that have no incoming arcs.
    See Also:
    Wikipedia: Graph traversal
    • Field Detail

      • g

        protected final Graph<? extends V,​? extends Edge<V>> g
    • Constructor Detail

      • TraversalFromRoots

        public TraversalFromRoots​(Graph<? extends V,​? extends Edge<V>> g)
        Constructs a traversal order of a graph.
        Parameters:
        g - a graph
    • Method Detail

      • track

        public abstract List<? extends GraphTraversal.Node<V>> track​(V root,
                                                                     int time)
        Runs the traversal algorithm on a graph from a designated root.
        Parameters:
        root - a root
        time - the initial time
        Returns:
        the nodes visited
      • traverse

        public List<V> traverse​(V root,
                                int time)
        Runs the traversal algorithm on a graph from a designated root.
        Parameters:
        root - a root
        time - the initial time
        Returns:
        the vertices visited