程序包 cn.denghanxi.s44

类 EdgeWeightedDirectedCycle

  • public class EdgeWeightedDirectedCycle
extends Object
    The

    EdgeWeightedDirectedCycle

    class represents a data type for determining whether an edge-weighted digraph has a directed cycle. The hasCycle operation determines whether the edge-weighted digraph has a directed cycle and, if so, the cycle operation returns one.

    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 hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.

    See Topological to compute a topological order if the edge-weighted digraph is acyclic.

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

    作者:
    Robert Sedgewick, Kevin Wayne

    • 构造器详细资料

      • EdgeWeightedDirectedCycle

        public EdgeWeightedDirectedCycle​(EdgeWeightedDigraph G)
        Determines whether the edge-weighted digraph

        G

        has a directed cycle and, if so, finds such a cycle.
        参数:
        G - the edge-weighted digraph

    • 方法详细资料

      • hasCycle

        public boolean hasCycle()
        Does the edge-weighted digraph have a directed cycle?
        返回:

        true

        if the edge-weighted digraph has a directed cycle,

        false

        otherwise

      • cycle

        public Iterable<DirectedEdge> cycle()
        Returns a directed cycle if the edge-weighted digraph has a directed cycle, and

        null

        otherwise.
        返回:
        a directed cycle (as an iterable) if the edge-weighted digraph has a directed cycle, and

        null

        otherwise