554
Graph Algorithms
If the network described is viewed as a graph, your task as network administrator is to
find the “shortest” path from one node to another in the graph. Because graphs have so
many applications, there is a great deal of interest in finding efficient algorithms to answer certain questions about graphs, directed graphs, or trees, and to perform certain
tasks on them, such as finding shortest paths. All graph algorithms use one of the convenient representations (adjacency matrix or adjacency list) presented in Chapter 6.
This chapter covers many of the “classical” graph algorithms. Section 7.1 first
relates directed graphs to binary relations, and reachability in a graph to the transitive closure of a binary relation. Then two different algorithms pertaining to reachability are given.
In Section 7.2 we will look at algorithms that answer two historically interesting questions about graphs. These questions are known as the highway inspector
problem and the traveling salesman problem. The highway inspector problem asks
whether there is a path through a given graph that uses each arc exactly once,
thereby providing an efficient way for a highway inspector to check all roads without going over the same road twice. The traveling salesman problem asks whether
there is a cycle in a given graph that visits each node of the graph and, if so, which
such cycle requires the minimum distance to travel. Recall that a cycle is a path
that ends where it started and does not use any other node more than once; thus
such a cycle would provide an efficient way for a salesperson to visit all cities in
the sales territory only once and end up at home.
Section 7.3 provides algorithmic solutions to the two problems of finding the
minimum path between two nodes in a simple, connected graph and of minimizing
the number of arcs used to connect all nodes in a simple, connected graph. Section 7.4
discusses algorithms for traversing simple graphs—“visiting” all the nodes in some
systematic way. Section 7.5 uses one of these traversal algorithms to detect articulation
points in a simple connected graph, points whose removal would disconnect the graph.
S e c t i o n 7 . 1 DirecteD Gr aphs anD Binary rel ations;
Warshall’s alGorithm
In this section we confine our attention to (unweighted) directed graphs with no
parallel arcs. (In a directed graph, two arcs from node a to node b would be parallel, but one arc from a to b and another from b to a are not parallel arcs.) Consider the adjacency matrix of the graph (assuming some arbitrary ordering of the
n nodes, which we always assume when discussing the adjacency matrix of a
graph). This will be an n × n matrix, not necessarily symmetric. Furthermore,
because there are no parallel arcs in the graph, the adjacency matrix will be a
Boolean matrix, that is, a matrix whose only elements are 0s and 1s. Conversely,
given an n × n Boolean matrix, we can reconstruct the directed graph that the
matrix represents, and it will have no parallel arcs. Thus there is a one-to-one
correspondence, which we can picture as
Directed graphs
with n nodes,
no parallel arcs
n × n Boolean
matrices
(1)
Now we will see how binary relations tie in to this correspondence.
Graph Algorithms
If the network described is viewed as a graph, your task as network administrator is to
find the “shortest” path from one node to another in the graph. Because graphs have so
many applications, there is a great deal of interest in finding efficient algorithms to answer certain questions about graphs, directed graphs, or trees, and to perform certain
tasks on them, such as finding shortest paths. All graph algorithms use one of the convenient representations (adjacency matrix or adjacency list) presented in Chapter 6.
This chapter covers many of the “classical” graph algorithms. Section 7.1 first
relates directed graphs to binary relations, and reachability in a graph to the transitive closure of a binary relation. Then two different algorithms pertaining to reachability are given.
In Section 7.2 we will look at algorithms that answer two historically interesting questions about graphs. These questions are known as the highway inspector
problem and the traveling salesman problem. The highway inspector problem asks
whether there is a path through a given graph that uses each arc exactly once,
thereby providing an efficient way for a highway inspector to check all roads without going over the same road twice. The traveling salesman problem asks whether
there is a cycle in a given graph that visits each node of the graph and, if so, which
such cycle requires the minimum distance to travel. Recall that a cycle is a path
that ends where it started and does not use any other node more than once; thus
such a cycle would provide an efficient way for a salesperson to visit all cities in
the sales territory only once and end up at home.
Section 7.3 provides algorithmic solutions to the two problems of finding the
minimum path between two nodes in a simple, connected graph and of minimizing
the number of arcs used to connect all nodes in a simple, connected graph. Section 7.4
discusses algorithms for traversing simple graphs—“visiting” all the nodes in some
systematic way. Section 7.5 uses one of these traversal algorithms to detect articulation
points in a simple connected graph, points whose removal would disconnect the graph.
S e c t i o n 7 . 1 DirecteD Gr aphs anD Binary rel ations;
Warshall’s alGorithm
In this section we confine our attention to (unweighted) directed graphs with no
parallel arcs. (In a directed graph, two arcs from node a to node b would be parallel, but one arc from a to b and another from b to a are not parallel arcs.) Consider the adjacency matrix of the graph (assuming some arbitrary ordering of the
n nodes, which we always assume when discussing the adjacency matrix of a
graph). This will be an n × n matrix, not necessarily symmetric. Furthermore,
because there are no parallel arcs in the graph, the adjacency matrix will be a
Boolean matrix, that is, a matrix whose only elements are 0s and 1s. Conversely,
given an n × n Boolean matrix, we can reconstruct the directed graph that the
matrix represents, and it will have no parallel arcs. Thus there is a one-to-one
correspondence, which we can picture as
Directed graphs
with n nodes,
no parallel arcs
n × n Boolean
matrices
(1)
Now we will see how binary relations tie in to this correspondence.