## Class Graph

• Object
• edu.princeton.cs.algs4.Graph

• public class Graph
extends Object
The Graph 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 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. 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 by adj(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
• ### Constructor Summary

Constructors
Constructor Description
Graph​(int V)
Initializes an empty graph with V vertices and 0 edges.
Graph​(Graph G)
Initializes a new graph that is a deep copy of G.
Graph​(In in)
Initializes a graph from the specified input stream.
• ### Method Summary

All Methods
Modifier and Type Method Description
void addEdge​(int v, int w)
Adds the undirected edge v-w to this graph.
Returns the vertices adjacent to vertex v.
int degree​(int v)
Returns the degree of vertex v.
int E()
Returns the number of edges in this graph.
static void main​(String[] args)
Unit tests the Graph 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 with V vertices and 0 edges. param V the number of vertices
Parameters:
V - number of vertices
Throws:
IllegalArgumentException - if V < 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 - if in is null
IllegalArgumentException - if the endpoints of any edge are not in prescribed range
IllegalArgumentException - if the number of vertices or edges is negative
IllegalArgumentException - if the input stream is in the wrong format
• #### Graph

public Graph​(Graph G)
Initializes a new graph that is a deep copy of G.
Parameters:
G - the graph to copy
Throws:
IllegalArgumentException - if G is null
• ### 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

public void addEdge​(int v,
int w)
Adds the undirected edge v-w to this graph.
Parameters:
v - one vertex in the edge
w - the other vertex in the edge
Throws:
IllegalArgumentException - unless both 0 <= v < V and 0 <= w < V

public Iterable<Integer> adj​(int v)
Returns the vertices adjacent to vertex v.
Parameters:
v - the vertex
Returns:
the vertices adjacent to vertex v, as an iterable
Throws:
IllegalArgumentException - unless 0 <= v < V
• #### degree

public int degree​(int v)
Returns the degree of vertex v.
Parameters:
v - the vertex
Returns:
the degree of vertex v
Throws:
IllegalArgumentException - unless 0 <= v < V
• #### toString

public String toString()
Returns a string representation of this graph.
Overrides:
toString in class Object
Returns:
the number of vertices V, followed by the number of edges E, followed by the V adjacency lists
• #### main

public static void main​(String[] args)
Unit tests the Graph data type.
Parameters:
args - the command-line arguments