程序包 edu.princeton.cs.algs4

类 TopologicalX

  • public class TopologicalX
extends java.lang.Object
    The TopologicalX class represents a data type for determining a topological order of a directed acyclic graph (DAG). Recall, a digraph has a topological order if and only if it is a DAG. The hasOrder operation determines whether the digraph has a topological order, and if so, the order operation returns one.

    This implementation uses a nonrecursive, queue-based algorithm. 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 hasOrder and rank operations takes constant time; the order operation takes time proportional to V.

    See DirectedCycle, DirectedCycleX, and EdgeWeightedDirectedCycle to compute a directed cycle if the digraph is not a DAG. See Topological for a recursive version that uses depth-first search.

    For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      TopologicalX​(Digraph G)
      Determines whether the digraph G has a topological order and, if so, finds such a topological order.
      TopologicalX​(EdgeWeightedDigraph G)
      Determines whether the edge-weighted digraph G has a topological order and, if so, finds such a topological order.

    • 方法概要

      修饰符和类型 方法 说明
      boolean hasOrder()
      Does the digraph have a topological order?
      static void main​(java.lang.String[] args)
      Unit tests the TopologicalX data type.
      java.lang.Iterable<java.lang.Integer> order()
      Returns a topological order if the digraph has a topologial order, and null otherwise.
      int rank​(int v)
      The the rank of vertex v in the topological order; -1 if the digraph is not a DAG

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

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

    • 构造器详细资料

      • TopologicalX

        public TopologicalX​(Digraph G)
        Determines whether the digraph G has a topological order and, if so, finds such a topological order.
        参数:
        G - the digraph

      • TopologicalX

        public TopologicalX​(EdgeWeightedDigraph G)
        Determines whether the edge-weighted digraph G has a topological order and, if so, finds such a topological order.
        参数:
        G - the digraph

    • 方法详细资料

      • order

        public java.lang.Iterable<java.lang.Integer> order()
        Returns a topological order if the digraph has a topologial order, and null otherwise.
        返回:
        a topological order of the vertices (as an interable) if the digraph has a topological order (or equivalently, if the digraph is a DAG), and null otherwise

      • hasOrder

        public boolean hasOrder()
        Does the digraph have a topological order?
        返回:
        true if the digraph has a topological order (or equivalently, if the digraph is a DAG), and false otherwise

      • rank

        public int rank​(int v)
        The the rank of vertex v in the topological order; -1 if the digraph is not a DAG
        参数:
        v - vertex
        返回:
        the position of vertex v in a topological order of the digraph; -1 if the digraph is not a DAG
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • main

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