Data Structures and Algorithms
with ObjectOriented Design Patterns in C++
Consider a directed graph as given by Definition .

Each element of is called a vertex
or a node of G.
Hence, is the set of vertices (or nodes) of G.

Each element of is called an edge
or an arc of G.
Hence, is the set of edges (or arcs) of G.

An edge can be represented as .
An arrow that points from v to w is known
as a directed arc .
Vertex w is called the head of the arc
because it is found at the arrow head.
Conversely, v is called the tail of the arc.
Finally, vertex w is said to be adjacent
to vertex v.

An edge e=(v,w) is said to
emanate from vertex v.
We use notation to denote the set of edges
emanating from vertex v.
I.e.,

The outdegree
of a node is the number of edges
emanating from that node.
Therefore, the outdegree of v is

An edge e=(v,w) is said to be
incident on vertex w.
We use notation to denote the set of edges
incident on vertex w.
I.e.,

The indegree
of a node is the number of edges
incident on that node.
Therefore, the indegree of w is
For example, Table enumerates the sets of
emanating and incident edges
and the in and outdegrees
for each of the vertices in graph shown in Figure .
There is still more terminology to be introduced,
but in order to do that,
we need the following definition:
Definition (Path and Path Length)
A path in a directed graph
is a nonempty sequence of vertices
where for
such that for .
The length of path P is k1.
For example, consider again the graph shown in Figure .
Among the paths contained in there is
the path of length zero, ;
the path of length one, ;
the path of length two, ; and so on.
In fact, this graph generates an infinite number of paths!
(To see how this is possible,
consider that is a path in ).
Notice too the subtle distinction between a path of length zero, say ,
and the path of length one .
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.