edu.princeton.cs.algs4

## 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 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 vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.

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 and Description
`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.
`Graph(int V)`
Initializes an empty graph with `V` vertices and 0 edges.
• ### Method Summary

Methods
Modifier and Type Method and Description
`void` ```addEdge(int v, int w)```
Adds the undirected edge v-w to this graph.
`Iterable<Integer>` `adj(int v)`
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.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`
• ### 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 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
• ### 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