程序包 edu.princeton.cs.algs4

类 EdgeWeightedGraph

  • public class EdgeWeightedGraph
extends java.lang.Object
    The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V – 1, where each undirected edge is of type Edge and has a real-valued weight. It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

    This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the edges incident to a given vertex, which takes time proportional to the number of such edges.

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

    • 构造器概要

      构造器 
      构造器 说明
      EdgeWeightedGraph​(int V)
      Initializes an empty edge-weighted graph with V vertices and 0 edges.
      EdgeWeightedGraph​(int V, int E)
      Initializes a random edge-weighted graph with V vertices and E edges.
      EdgeWeightedGraph​(EdgeWeightedGraph G)
      Initializes a new edge-weighted graph that is a deep copy of G.
      EdgeWeightedGraph​(In in)
      Initializes an edge-weighted graph from an input stream.

    • 方法概要

      修饰符和类型 方法 说明
      void addEdge​(Edge e)
      Adds the undirected edge e to this edge-weighted graph.
      java.lang.Iterable<Edge> adj​(int v)
      Returns the edges incident on vertex v.
      int degree​(int v)
      Returns the degree of vertex v.
      int E()
      Returns the number of edges in this edge-weighted graph.
      java.lang.Iterable<Edge> edges()
      Returns all edges in this edge-weighted graph.
      static void main​(java.lang.String[] args)
      Unit tests the EdgeWeightedGraph data type.
      java.lang.String toString()
      Returns a string representation of the edge-weighted graph.
      int V()
      Returns the number of vertices in this edge-weighted graph.

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

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

    • 构造器详细资料

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(int V)
        Initializes an empty edge-weighted graph with V vertices and 0 edges.
        参数:
        V - the number of vertices
        抛出:
        java.lang.IllegalArgumentException - if V < 0

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(int V,
                         int E)
        Initializes a random edge-weighted graph with V vertices and E edges.
        参数:
        V - the number of vertices
        E - the number of edges
        抛出:
        java.lang.IllegalArgumentException - if V < 0
        java.lang.IllegalArgumentException - if E < 0

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(In in)
        Initializes an edge-weighted graph from an input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices and edge weights, with each entry separated by whitespace.
        参数:
        in - the input stream
        抛出:
        java.lang.IllegalArgumentException - if the endpoints of any edge are not in prescribed range
        java.lang.IllegalArgumentException - if the number of vertices or edges is negative

      • EdgeWeightedGraph

        public EdgeWeightedGraph​(EdgeWeightedGraph G)
        Initializes a new edge-weighted graph that is a deep copy of G.
        参数:
        G - the edge-weighted graph to copy

    • 方法详细资料

      • V

        public int V()
        Returns the number of vertices in this edge-weighted graph.
        返回:
        the number of vertices in this edge-weighted graph

      • E

        public int E()
        Returns the number of edges in this edge-weighted graph.
        返回:
        the number of edges in this edge-weighted graph

      • addEdge

        public void addEdge​(Edge e)
        Adds the undirected edge e to this edge-weighted graph.
        参数:
        e - the edge
        抛出:
        java.lang.IllegalArgumentException - unless both endpoints are between 0 and V-1

      • adj

        public java.lang.Iterable<Edge> adj​(int v)
        Returns the edges incident on vertex v.
        参数:
        v - the vertex
        返回:
        the edges incident on vertex v as an Iterable
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • degree

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

      • edges

        public java.lang.Iterable<Edge> edges()
        Returns all edges in this edge-weighted graph. To iterate over the edges in this edge-weighted graph, use foreach notation: for (Edge e : G.edges()).
        返回:
        all edges in this edge-weighted graph, as an iterable

      • toString

        public java.lang.String toString()
        Returns a string representation of the edge-weighted graph. This method takes time proportional to E + V.
        覆盖:
        toString 在类中 java.lang.Object
        返回:
        the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges

      • main

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