Chapter 16. Graph Algorithms
Graphs are flexible data structures that model problems defined in terms of relationships or connections between objects (see Chapter 11). This chapter presents algorithms that work with graphs. As we will see, many graph algorithms resemble the fundamental ones for breadth-first and depth-first search introduced in Chapter 11. Breadth-first and depth-first search are important to many other graph algorithms because they offer good ways of exploring the structure of a graph in a systematic manner.
One significant difference between the algorithms of Chapter 11 and the ones in this chapter, however, is that the algorithms here work with weighted graphs. In a weighted graph , each edge is assigned a value, or weight, which is represented pictorially as a small number beside the edge. Although weights can mean many things, in general they represent a cost associated with traversing an edge. Weighted graphs and their algorithms have an enormous capacity to model real problems. Example 16.1 is a header for the graph algorithms presented in this chapter.
This chapter covers:
- Minimum spanning trees
Trees that serve as abstractions of many connectivity problems. A minimum spanning tree is a tree that connects all vertices in an undirected, weighted graph at a minimum cost.
- Shortest paths
The result of solving various types of shortest-path problems. A shortest path is a path that connects one vertex to another in a directed, weighted graph at a minimum cost.
- Traveling-salesman problem
A surprisingly difficult problem in which we look for the shortest tour that visits every vertex in a complete, undirected, weighted graph exactly once before returning to the first vertex.
Some applications of graph algorithms are:
- Efficient pipelines
A practical concern in transporting water, oil, and other liquids. If distribution points for the pipeline are represented as vertices in a graph, and candidate connections between the points as edges are weighted by the cost to connect the points, a minimum spanning tree gives us the best way to lay a pipeline that connects all of the distribution points.
- Routing tables (illustrated in this chapter)
Tables used by routers to help direct data through an internet. The purpose of a router is to move data closer to its final destination. In one type of routing, routers periodically compute shortest paths to one another so each knows the best next step for sending data to certain destinations.
- Delivery services
Services that typically visit numerous locations to pick up and deliver packages. Solving the traveling-salesman problem can indicate the most efficient way for a vehicle operated by a service to visit every location exactly once before returning to its starting point.
- Communication networks
Networks containing many different types of equipment including telephone lines, relay stations, and satellite systems, all of which must be located in an optimal manner. An optimal arrangement can be determined by computing a minimum spanning tree for the weighted graph that models the network.
- Routing airplanes
An optimization problem particularly important to airlines and air traffic control agencies. Often airplanes cannot fly directly from one point to another. Instead, they weave their way through airway structures, or highways in the sky, considering winds, monetary charges for traversing airspace, and air traffic control restrictions. The best route between two points is the path with the minimum weight defined in terms of factors like these.
- Closed transport systems
Systems in which railroad cars or conveyor carts repeatedly tour several points. Systems like these might be used to deliver parts in a factory or to move inventory in and out of a warehouse. Solving the traveling-salesman problem can indicate the best way to construct the system.
- Wiring circuit boards
An optimization problem in electronics manufacturing. Often it is necessary to make the pins of several components on a circuit board electrically equivalent by establishing a connection between them. If each pin is represented as a vertex in a graph, and candidate connections as edges weighted by the amount of wire required for the connection, a minimum spanning tree gives us the best way to connect the pins.
- Traffic monitoring
The process of watching changes in traffic flow to determine the best route between two points in a city. To avoid excessive traffic delays, we can use a weighted graph to model the flow of traffic along roadways and look for the path from intersection to intersection with the minimum traffic.
/*****************************************************************************
* *
* ------------------------------ graphalg.h ------------------------------ *
* *
*****************************************************************************/
#ifndef GRAPHALG_H
#define GRAPHALG_H
#include "graph.h"
#include "list.h"
/*****************************************************************************
* *
* Define a structure for vertices in minimum spanning trees. *
* *
*****************************************************************************/
typedef struct MstVertex_ {
void *data;
double weight;
VertexColor color;
double key;
struct MstVertex_ *parent;
} MstVertex;
/*****************************************************************************
* *
* Define a structure for vertices in shortest-path problems. *
* *
*****************************************************************************/
typedef struct PathVertex_ {
void *data;
double weight;
VertexColor color;
double d;
struct PathVertex_ *parent;
} PathVertex;
/*****************************************************************************
* *
* Define a structure for vertices in traveling-salesman problems. *
* *
*****************************************************************************/
typedef struct TspVertex_ {
void *data;
double x,
y;
VertexColor color;
} TspVertex;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
int mst(Graph *graph, const MstVertex *start, List *span, int (*match)(const
void *key1, const void *key2));
int shortest(Graph *graph, const PathVertex *start, List *paths, int (*match)
(const void *key1, const void *key2));
int tsp(List *vertices, const TspVertex *start, List *tour, int (*match)
(const void *key1, const void *key2));
#endif