Java Reference
In-Depth Information
0
2
4
1
3
4
7
1
2
1
3
(A)
(B)
(C)
Figure11.1
Examples of graphs and terminology. (a) A graph. (b) A directed
graph (digraph). (c) A labeled (directed) graph with weights associated with the
edges. In this example, there is a simple path from Vertex 0 to Vertex 3 containing
Vertices 0, 1, and 3. Vertices 0, 1, 3, 2, 4, and 1 also form a path, but not a simple
path because Vertex 1 appears twice. Vertices 1, 3, 2, 4, and 1 form a simple cycle.
11.1
Terminology and Representations
A graph G = (V; E) consists of a set of vertices V and a set of edges E, such
that each edge in E is a connection between a pair of vertices in V.
1
The number
of vertices is written jVj, and the number of edges is written jEj. jEj can range
from zero to a maximum of jVj
2
jVj. A graph with relatively few edges is called
sparse, while a graph with many edges is called dense.
A graph containing all
possible edges is said to be complete.
A graph with edges directed from one vertex to another (as in Figure 11.1(b))
is called a directed graph or digraph. A graph whose edges are not directed is
called an undirected graph (as illustrated by Figure 11.1(a)). A graph with labels
associated with its vertices (as in Figure 11.1(c)) is called a labeled graph. Two
vertices are adjacent if they are joined by an edge. Such vertices are also called
neighbors. An edge connecting Vertices U and V is written (U, V). Such an edge
is said to be incident on Vertices U and V. Associated with each edge may be a
cost or weight. Graphs whose edges have weights (as in Figure 11.1(c)) are said to
be weighted.
A sequence of vertices v
1
, v
2
, ..., v
n
forms a path of length n 1 if there exist
edges from v
i
to v
i+1
for 1 i < n. A path is simple if all vertices on the path are
distinct. The length of a path is the number of edges it contains. A cycle is a path
of length three or more that connects some vertex v
1
to itself. A cycle is simple if
the path is simple, except for the first and last vertices being the same.
1
Some graph applications require that a given pair of vertices can have multiple or parallel edges
connecting them, or that a vertex can have an edge to itself. However, the applications discussed
in this topic do not require either of these special cases, so for simplicity we will assume that they
cannot occur.
