edu.princeton.cs.algs4

Class Graph

java.lang.Object

edu.princeton.cs.algs4.Graph

public class Graph
extends java.lang.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.

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

Modifier and Type	Method and Description
void	addEdge(int v, int w) Adds the undirected edge v-w to this graph.
java.lang.Iterable<java.lang.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(java.lang.String[] args) Unit tests the Graph data type.
java.lang.String	toString() Returns a string representation of this graph.
int	V() Returns the number of vertices in this graph.

Methods inherited from class java.lang.Object

equals, 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:

java.lang.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:

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

java.lang.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

addEdge

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:

java.lang.IllegalArgumentException - unless both 0 <= v < V and 0 <= w < V

adj

public java.lang.Iterable<java.lang.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:

java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

toString

public java.lang.String toString()

Returns a string representation of this graph.

Overrides:

toString in class java.lang.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(java.lang.String[] args)

Unit tests the Graph data type.

Parameters:

args - the command-line arguments