程序包 edu.princeton.cs.algs4

类 GlobalMincut

  • public class GlobalMincut
extends java.lang.Object
    The GlobalMincut class represents a data type for computing a global minimum cut in an edge-weighted graph where the edge weights are nonnegative. A cut is a partition of the set of vertices of a graph into two nonempty subsets. An edge that has one endpoint in each subset of a cut is a crossing edge. The weight of a cut is the sum of the weights of its crossing edges. A global minimum cut is a cut for which the weight is not larger than the weight of any other cut.

    The weight() method returns the weight of the minimum cut and the cut(int v) method determines if a vertex v is on the first or on the second subset of vertices of the minimum cut.

    This is an implementation of Stoer–Wagner's algorithm using an index priority queue and the union-find data type in order to simplify dealing with contracting edges. Precisely, the index priority queue is an instance of IndexMaxPQ which is based on a binary heap. As a consequence, the constructor takes O(V (V + E ) log V ) time and O(V) extra space (not including the graph), where V is the number of vertices and E is the number of edges. However, this time can be reduced to O(V E + V2 log V) by using an index priority queue implemented using Fibonacci heaps.

    Afterwards, the weight() and cut(int v) methods take constant time.

    For additional documentation, see

    • M. Stoer and F. Wagner (1997). A simple min-cut algorithm. Journal of the ACM , 44(4):585-591.

    • 方法概要

      修饰符和类型 方法 说明
      boolean cut​(int v)
      Returns true if the vertex v is on the first subset of vertices of the minimum cut; or false if the vertex v is on the second subset.
      static void main​(java.lang.String[] args)
      Unit tests the GlobalMincut data type.
      double weight()
      Returns the weight of the minimum cut.

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

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

    • 构造器详细资料

      • GlobalMincut

        public GlobalMincut​(EdgeWeightedGraph G)
        Computes a minimum cut of an edge-weighted graph.
        参数:
        G - the edge-weighted graph
        抛出:
        java.lang.IllegalArgumentException - if the number of vertices of G is less than 2 or if anny edge weight is negative

    • 方法详细资料

      • weight

        public double weight()
        Returns the weight of the minimum cut.
        返回:
        the weight of the minimum cut

      • cut

        public boolean cut​(int v)
        Returns true if the vertex v is on the first subset of vertices of the minimum cut; or false if the vertex v is on the second subset.
        参数:
        v - the vertex to check
        返回:
        true if the vertex v is on the first subset of vertices of the minimum cut; or false if the vertex v is on the second subset.
        抛出:
        java.lang.IllegalArgumentException - unless vertex v is between 0 and (G.V() - 1)

      • main

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