Package edu.princeton.cs.algs4
Class Graph
 Object

 edu.princeton.cs.algs4.Graph

public class Graph extends Object
TheGraph
class represents an undirected graph of vertices named 0 through V – 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent 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 vertices returned byadj(int)
takes time proportional to the degree of the vertex.) Constructing an empty graph with V vertices takes Θ(V) time; constructing a graph with E edges and V vertices takes Θ(E + V) time.For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(int v, int w)
Adds the undirected edge vw to this graph.Iterable<Integer>
adj(int v)
Returns the vertices adjacent to vertexv
.int
degree(int v)
Returns the degree of vertexv
.int
E()
Returns the number of edges in this graph.static void
main(String[] args)
Unit tests theGraph
data type.String
toString()
Returns a string representation of this graph.int
V()
Returns the number of vertices in this graph.



Constructor Detail

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

Graph
public Graph(In in)
Initializes a graph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, 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 negativeIllegalArgumentException
 if the input stream is in the wrong format

Graph
public Graph(Graph G)
Initializes a new graph that is a deep copy ofG
. Parameters:
G
 the graph to copy Throws:
IllegalArgumentException
 ifG
isnull


Method Detail

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

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

addEdge
public void addEdge(int v, int w)
Adds the undirected edge vw to this graph. Parameters:
v
 one vertex in the edgew
 the other vertex in the edge Throws:
IllegalArgumentException
 unless both0 <= v < V
and0 <= w < V

adj
public Iterable<Integer> adj(int v)
Returns the vertices adjacent to vertexv
. Parameters:
v
 the vertex Returns:
 the vertices adjacent to 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

toString
public String toString()
Returns a string representation of this graph.

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

