程序包 edu.princeton.cs.algs4

类 DepthFirstOrder

  • public class DepthFirstOrder
extends java.lang.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.

    • 方法概要

      修饰符和类型 方法 说明
      static void main​(java.lang.String[] args)
      Unit tests the DepthFirstOrder data type.
      java.lang.Iterable<java.lang.Integer> post()
      Returns the vertices in postorder.
      int post​(int v)
      Returns the postorder number of vertex v.
      java.lang.Iterable<java.lang.Integer> pre()
      Returns the vertices in preorder.
      int pre​(int v)
      Returns the preorder number of vertex v.
      java.lang.Iterable<java.lang.Integer> reversePost()
      Returns the vertices in reverse postorder.

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 构造器详细资料

      • DepthFirstOrder

        public DepthFirstOrder​(Digraph G)
        Determines a depth-first order for the digraph G.
        参数:
        G - the digraph

      • DepthFirstOrder

        public DepthFirstOrder​(EdgeWeightedDigraph G)
        Determines a depth-first order for the edge-weighted digraph G.
        参数:
        G - the edge-weighted digraph

    • 方法详细资料

      • pre

        public int pre​(int v)
        Returns the preorder number of vertex v.
        参数:
        v - the vertex
        返回:
        the preorder number of vertex v
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • post

        public int post​(int v)
        Returns the postorder number of vertex v.
        参数:
        v - the vertex
        返回:
        the postorder number of vertex v
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • post

        public java.lang.Iterable<java.lang.Integer> post()
        Returns the vertices in postorder.
        返回:
        the vertices in postorder, as an iterable of vertices

      • pre

        public java.lang.Iterable<java.lang.Integer> pre()
        Returns the vertices in preorder.
        返回:
        the vertices in preorder, as an iterable of vertices

      • reversePost

        public java.lang.Iterable<java.lang.Integer> reversePost()
        Returns the vertices in reverse postorder.
        返回:
        the vertices in reverse postorder, as an iterable of vertices

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the DepthFirstOrder data type.
        参数:
        args - the command-line arguments