程序包 edu.princeton.cs.algs4

类 CC

  • public class CC
extends java.lang.Object
    The CC class represents a data type for determining the connected components in an undirected graph. The id operation determines in which connected component a given vertex lies; the connected operation determines whether two vertices are in the same connected component; the count operation determines the number of connected components; and the size operation determines the number of vertices in the connect component containing a given vertex. The component identifier of a connected component is one of the vertices in the connected component: two vertices have the same component identifier if and only if they are in the same connected component.

    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 id, count, connected, and size operations take constant time.

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

    • 构造器概要

      构造器 
      构造器 说明
      CC​(EdgeWeightedGraph G)
      Computes the connected components of the edge-weighted graph G.
      CC​(Graph G)
      Computes the connected components of the undirected graph G.

    • 方法概要

      修饰符和类型 方法 说明
      boolean areConnected​(int v, int w)
      已过时。
      Replaced by connected(int, int).
      boolean connected​(int v, int w)
      Returns true if vertices v and w are in the same connected component.
      int count()
      Returns the number of connected components in the graph G.
      int id​(int v)
      Returns the component id of the connected component containing vertex v.
      static void main​(java.lang.String[] args)
      Unit tests the CC data type.
      int size​(int v)
      Returns the number of vertices in the connected component containing vertex v.

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

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

    • 构造器详细资料

      • CC

        public CC​(Graph G)
        Computes the connected components of the undirected graph G.
        参数:
        G - the undirected graph

      • CC

        public CC​(EdgeWeightedGraph G)
        Computes the connected components of the edge-weighted graph G.
        参数:
        G - the edge-weighted graph

    • 方法详细资料

      • id

        public int id​(int v)
        Returns the component id of the connected component containing vertex v.
        参数:
        v - the vertex
        返回:
        the component id of the connected component containing vertex v
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • size

        public int size​(int v)
        Returns the number of vertices in the connected component containing vertex v.
        参数:
        v - the vertex
        返回:
        the number of vertices in the connected component containing vertex v
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • count

        public int count()
        Returns the number of connected components in the graph G.
        返回:
        the number of connected components in the graph G

      • connected

        public boolean connected​(int v,
                         int w)
        Returns true if vertices v and w are in the same connected component.
        参数:
        v - one vertex
        w - the other vertex
        返回:
        true if vertices v and w are in the same connected component; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V
        java.lang.IllegalArgumentException - unless 0 <= w < V

      • areConnected

        @Deprecated
public boolean areConnected​(int v,
                            int w)
        已过时。
        Replaced by connected(int, int).
        Returns true if vertices v and w are in the same connected component.
        参数:
        v - one vertex
        w - the other vertex
        返回:
        true if vertices v and w are in the same connected component; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V
        java.lang.IllegalArgumentException - unless 0 <= w < V

      • main

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