144 GRAPH ALGORITHMS
to get information through. The last section of this chapter looks at a bicon-
nected components algorithm. It will identify nodes in a graph that are on
every path from one part of the graph to another. These nodes are points in a
computer network, for example, where a failure could cause the network to
become disconnected.6.1 Graph Background and Terminology
Formally, a graph is an ordered pair, G = (V,E), of two sets representing the
nodes or vertices of the graph and the edges of the graph. An edge specifies
which nodes have a connection between them. When working with graphs,
we are frequently interested in how these edges can be put together to move
through the graph. For this reason, we will often talk of traveling an edge,
which means that we have changed our node of interest by following one of
the edges connected to it. In other words, if our graph has nodes A and B that
are connected by an edge, we will talk of “moving from A to B,” “traveling
from A to B,” or “traversing the edge from A to B” to represent the fact that
our focus has changed from node A to node B. For the ease of discussion, we
will just write the two node labels as shorthand for the edge that connects
them. So, AB would represent the edge between node A and node B, and we
will say that B is adjacent to A.
A graph can either be undirected or directed. An undirected graph, typically
just called a graph, has edges that can be traversed in either direction. In this
case, an edge is a set, which contains the labels of the nodes that are at the two
ends of the edge.^1 A directed graph, also called a digraph, has edges that can
only be traversed in one direction. For a digraph, our set of edges will have
ordered pairs in which the first item is where the edge starts and the second is
where the edge ends.^2 In our discussion, we will use the shorthand above for
our edges, with the context indicating if this is a directed edge or if you can
travel in either direction between the two nodes.(^1) If a set representing an edge has just one element, that represents an edge that “loops,”
or in other words, starts and ends at the same node.
(^2) In a digraph, an ordered pair that has the same label for both components represents
an edge that starts and ends on the same node.