GRAPH ALGORITHMS 143edges. Sometimes our graphs are directed (like one-way streets) or weighted
with a travel cost associated with each edge (like toll roads). As we give more
details on the terminology and concepts in graphs, the similarity to road maps
will be even clearer.
After we have explored the mathematical concepts of graphs, we will look
at methods of storing them so that they can be used and manipulated by our
algorithms. We will see that there are alternatives for graph storage that vary in
the amount of overhead, which depends on the graph itself.
There are times when information needs to be distributed to a large number
of people or to the computers on a large network. We would like this informa-
tion to get to everywhere, but we also don’t want it going any place twice.
Some groups of people will accomplish this by setting up a “phone tree” where
each person has a small number of people to call to pass on news. If everyone
appears once in the tree and if the tree is not very deep, information will travel
to everyone very quickly. For graphs, this is a bit more complicated, because
there are typically many more connections between nodes than in a tree. We
will look at two graph traversal methods, depth-first and breadth-first, to
accomplish this.
A spanning tree is a connected subset of a graph that has no cycles and con-
tains all of the graph nodes and a subset of the edges. A minimum spanning
tree is a spanning tree where the sum of the weights for the edges included has
the smallest total possible. One use of a minimum spanning tree is in the con-
struction of a company intranet with routers to be placed at strategic points
throughout some geographic area. If we wish to minimize the cost of connect-
ing the routers, we could build a graph with each router as a node and the
weights on the edges set as the cost of connecting each pair of routers. The
minimum spanning tree of this graph will tell us which pairs of routers to con-
nect with wires so that our intranet is completely connected at the cheapest
cost.
A similar application is to find the shortest path between two nodes of a
graph. This has a practical application in planning a route for a car trip or send-
ing a message through a computer network.
An important consideration in large computer networks is reliability. We
would like the network to continue to function if one of the routers should
fail. In simple terms, this requires multiple paths between any two routers in
the network so that if something fails along one of the paths, there is still a way