Class Graph

java.lang.Object

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.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of @link{Bag} objects. All operations take constant time (in the worst case) except iterating over the neighbors of a vertex, which takes time proportional to the number of neighbors.

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 an 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.
java.lang.Iterable<java.lang.Integer>	adj(int v) Returns the vertices adjacent to 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 the graph.
int	V() Returns the number of vertices in this graph.

Methods inherited from class java.lang.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

Throws:

java.lang.IllegalArgumentException - if V < 0

Graph

public Graph(In in)

Initializes a 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, with each entry separated by whitespace.

Parameters:

in - the input stream

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.IndexOutOfBoundsException - 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.IndexOutOfBoundsException - unless 0 <= v < V

toString

public java.lang.String toString()

Returns a string representation of the 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.