程序包 edu.princeton.cs.algs4

类 WeightedQuickUnionUF

  • public class WeightedQuickUnionUF
extends java.lang.Object
    The WeightedQuickUnionUF class represents a union–find data type (also known as the disjoint-sets data type). It supports the union and find operations, along with a connected operation for determining whether two sites are in the same component and a count operation that returns the total number of components.

    The union–find data type models connectivity among a set of n sites, named 0 through n–1. The is-connected-to relation must be an equivalence relation:

    • Reflexive: p is connected to p.
    • Symmetric: If p is connected to q, then q is connected to p.
    • Transitive: If p is connected to q and q is connected to r, then p is connected to r.

    An equivalence relation partitions the sites into equivalence classes (or components). In this case, two sites are in the same component if and only if they are connected. Both sites and components are identified with integers between 0 and n–1. Initially, there are n components, with each site in its own component. The component identifier of a component (also known as the root, canonical element, leader, or set representative) is one of the sites in the component: two sites have the same component identifier if and only if they are in the same component.

    • union(p, q) adds a connection between the two sites p and q. If p and q are in different components, then it replaces these two components with a new component that is the union of the two.
    • find(p) returns the component identifier of the component containing p.
    • connected(p, q) returns true if both p and q are in the same component, and false otherwise.
    • count() returns the number of components.

    The component identifier of a component can change only when the component itself changes during a call to union—it cannot change during a call to find, connected, or count.

    This implementation uses weighted quick union by size (without path compression). Initializing a data structure with n sites takes linear time. Afterwards, the union, find, and connected operations take logarithmic time (in the worst case) and the count operation takes constant time. For alternate implementations of the same API, see UF, QuickFindUF, and QuickUnionUF.

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

    • 构造器概要

      构造器 
      构造器 说明
      WeightedQuickUnionUF​(int n)
      Initializes an empty union–find data structure with n sites 0 through n-1.

    • 方法概要

      修饰符和类型 方法 说明
      boolean connected​(int p, int q)
      Returns true if the the two sites are in the same component.
      int count()
      Returns the number of components.
      int find​(int p)
      Returns the component identifier for the component containing site p.
      static void main​(java.lang.String[] args)
      Reads in a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer represents some object; if the sites are in different components, merge the two components and print the pair to standard output.
      void union​(int p, int q)
      Merges the component containing site p with the the component containing site q.

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

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

    • 构造器详细资料

      • WeightedQuickUnionUF

        public WeightedQuickUnionUF​(int n)
        Initializes an empty union–find data structure with n sites 0 through n-1. Each site is initially in its own component.
        参数:
        n - the number of sites
        抛出:
        java.lang.IllegalArgumentException - if n < 0

    • 方法详细资料

      • count

        public int count()
        Returns the number of components.
        返回:
        the number of components (between 1 and n)

      • find

        public int find​(int p)
        Returns the component identifier for the component containing site p.
        参数:
        p - the integer representing one object
        返回:
        the component identifier for the component containing site p
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= p < n

      • connected

        public boolean connected​(int p,
                         int q)
        Returns true if the the two sites are in the same component.
        参数:
        p - the integer representing one site
        q - the integer representing the other site
        返回:
        true if the two sites p and q are in the same component; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless both 0 <= p < n and 0 <= q < n

      • union

        public void union​(int p,
                  int q)
        Merges the component containing site p with the the component containing site q.
        参数:
        p - the integer representing one site
        q - the integer representing the other site
        抛出:
        java.lang.IllegalArgumentException - unless both 0 <= p < n and 0 <= q < n

      • main

        public static void main​(java.lang.String[] args)
        Reads in a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer represents some object; if the sites are in different components, merge the two components and print the pair to standard output.
        参数:
        args - the command-line arguments