程序包 edu.princeton.cs.algs4

类 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.

构造器概要

构造器

构造器	说明
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.

方法概要

修饰符和类型	方法	说明
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.

从类继承的方法 java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

构造器详细资料

Graph

public Graph(int V)

Initializes an empty graph with V vertices and 0 edges. param V the number of vertices

参数:

V - number of vertices

抛出:

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.

参数:

in - the input stream

抛出:

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.

参数:

G - the graph to copy

方法详细资料

V

public int V()

Returns the number of vertices in this graph.

返回:

the number of vertices in this graph

E

public int E()

Returns the number of edges in this graph.

返回:

the number of edges in this graph

addEdge

public void addEdge(int v,
                    int w)

Adds the undirected edge v-w to this graph.

参数:

v - one vertex in the edge

w - the other vertex in the edge

抛出:

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.

参数:

v - the vertex

返回:

the vertices adjacent to vertex v, as an iterable

抛出:

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

degree

public int degree(int v)

Returns the degree of vertex v.

参数:

v - the vertex

返回:

the degree of vertex v

抛出:

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

toString

public java.lang.String toString()

Returns a string representation of this graph.

覆盖:

toString 在类中 java.lang.Object

返回:

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.

参数:

args - the command-line arguments