edu.princeton.cs.algorithms

Class Graph

java.lang.Object

edu.princeton.cs.algorithms.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.

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(edu.princeton.cs.introcs.In in) Initializes a graph from an 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 the graph.
Iterable<Integer>	adj(int v) Returns the vertices adjacent to vertex v.
int	E() Returns the number of edges in the graph.
static void	main(String[] args) Unit tests the Graph data type.
String	toString() Returns a string representation of the graph.
int	V() Returns the number of vertices in the 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:

IllegalArgumentException - if V < 0

Graph

public Graph(edu.princeton.cs.introcs.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

Throws:

IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range

IllegalArgumentException - if the number of vertices or edges is negative

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 the graph.

Returns:

the number of vertices in the graph

E

public int E()

Returns the number of edges in the graph.

Returns:

the number of edges in the graph

addEdge

public void addEdge(int v,
                    int w)

Adds the undirected edge v-w to the graph.

Parameters:

v - one vertex in the edge

w - the other vertex in the edge

Throws:

IndexOutOfBoundsException - unless both 0 <= v < V and 0 <= w < V

adj

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:

IndexOutOfBoundsException - unless 0 <= v < V

toString

public String toString()

Returns a string representation of the graph. This method takes time proportional to E + V.

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.