Package edu.princeton.cs.algs4
Class EdgeWeightedGraph
 Object

 edu.princeton.cs.algs4.EdgeWeightedGraph

public class EdgeWeightedGraph extends Object
TheEdgeWeightedGraph
class represents an edgeweighted graph of vertices named 0 through V – 1, where each undirected edge is of typeEdge
and has a realvalued 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 degree of a vertex, the number of vertices V in the graph, and the number of edges E in the graph. Parallel edges and selfloops are permitted. By convention, a selfloop vv appears in the adjacency list of v twice and contributes two to the degree of v.This implementation uses an adjacencylists representation, which is a vertexindexed array of
Bag
objects. It uses Θ(E + V) space, where E is the number of edges and V is the number of vertices. All instance methods take Θ(1) time. (Though, iterating over the edges returned byadj(int)
takes time proportional to the degree of the vertex.) Constructing an empty edgeweighted graph with V vertices takes Θ(V) time; constructing an edgeweighted graph with E edges and V vertices takes Θ(E + V) time.For additional documentation, see Section 4.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description EdgeWeightedGraph(int V)
Initializes an empty edgeweighted graph withV
vertices and 0 edges.EdgeWeightedGraph(int V, int E)
Initializes a random edgeweighted graph withV
vertices and E edges.EdgeWeightedGraph(EdgeWeightedGraph G)
Initializes a new edgeweighted graph that is a deep copy ofG
.EdgeWeightedGraph(In in)
Initializes an edgeweighted graph from an input stream.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(Edge e)
Adds the undirected edgee
to this edgeweighted graph.Iterable<Edge>
adj(int v)
Returns the edges incident on vertexv
.int
degree(int v)
Returns the degree of vertexv
.int
E()
Returns the number of edges in this edgeweighted graph.Iterable<Edge>
edges()
Returns all edges in this edgeweighted graph.static void
main(String[] args)
Unit tests theEdgeWeightedGraph
data type.String
toString()
Returns a string representation of the edgeweighted graph.int
V()
Returns the number of vertices in this edgeweighted graph.



Constructor Detail

EdgeWeightedGraph
public EdgeWeightedGraph(int V)
Initializes an empty edgeweighted graph withV
vertices and 0 edges. Parameters:
V
 the number of vertices Throws:
IllegalArgumentException
 ifV < 0

EdgeWeightedGraph
public EdgeWeightedGraph(int V, int E)
Initializes a random edgeweighted graph withV
vertices and E edges. Parameters:
V
 the number of verticesE
 the number of edges Throws:
IllegalArgumentException
 ifV < 0
IllegalArgumentException
 ifE < 0

EdgeWeightedGraph
public EdgeWeightedGraph(In in)
Initializes an edgeweighted 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. Parameters:
in
 the input stream Throws:
IllegalArgumentException
 ifin
isnull
IllegalArgumentException
 if the endpoints of any edge are not in prescribed rangeIllegalArgumentException
 if the number of vertices or edges is negative

EdgeWeightedGraph
public EdgeWeightedGraph(EdgeWeightedGraph G)
Initializes a new edgeweighted graph that is a deep copy ofG
. Parameters:
G
 the edgeweighted graph to copy


Method Detail

V
public int V()
Returns the number of vertices in this edgeweighted graph. Returns:
 the number of vertices in this edgeweighted graph

E
public int E()
Returns the number of edges in this edgeweighted graph. Returns:
 the number of edges in this edgeweighted graph

addEdge
public void addEdge(Edge e)
Adds the undirected edgee
to this edgeweighted graph. Parameters:
e
 the edge Throws:
IllegalArgumentException
 unless both endpoints are between0
andV1

adj
public Iterable<Edge> adj(int v)
Returns the edges incident on vertexv
. Parameters:
v
 the vertex Returns:
 the edges incident on vertex
v
as an Iterable  Throws:
IllegalArgumentException
 unless0 <= v < V

degree
public int degree(int v)
Returns the degree of vertexv
. Parameters:
v
 the vertex Returns:
 the degree of vertex
v
 Throws:
IllegalArgumentException
 unless0 <= v < V

edges
public Iterable<Edge> edges()
Returns all edges in this edgeweighted graph. To iterate over the edges in this edgeweighted graph, use foreach notation:for (Edge e : G.edges())
. Returns:
 all edges in this edgeweighted graph, as an iterable

toString
public String toString()
Returns a string representation of the edgeweighted graph. This method takes time proportional to E + V.

main
public static void main(String[] args)
Unit tests theEdgeWeightedGraph
data type. Parameters:
args
 the commandline arguments

