Many graph algorithms are based on graph searches. A graph search is an algorithm scheme that visits vertices or vertices and edges in a graph, in an order based on the connectivity of the graph. The most general searches visit both edges and vertices. At the time that an edge is visited, it goes from a vertex that has already been visited to a vertex that has not yet been visited. At the same time, the search visits the previously unvisited vertex. For simple applications, a search may only need to visit vertices. Then at the time that a vertex is visited, it is a neighbor of a vertex that was previously visited.
In a graph search, edges are visited at most once and not all edges are visited. The ones that are visited form a spanning tree for the vertices that are connected to the starting vertex by a path. A spanning tree for a set of vertices W is a set of edges without cycles that connects W. So in a spanning tree, there is exactly one path between any two of the vertices. This is the underlying reason for the utility of graph searches.
Graph searches make use of dispensers, which includes stacks, queues, and priority queues. The different types of dispensers and the variety of ways of prioritizing priority queues determine different orders of searching. This allows graph searches to be tailored to produces minimal spanning trees satisfying a variety of conditions.
Graph searches require a data structure that temporarily holds vertices that are neighbors of previously visited vertices, or edges that leave previously visited vertices. The data structures that are used form a family of abstract data types called dispensers.
A dispenser is an abstract data type that supports insert, delete, and retrieve operations. The dispenser family is characterized by the fact that whenever it is not empty, only one of its data items is accessible for delete or retrieve operations.
Stacks, queues, and priority queues are the best-known abstract data types in the dispenser family. They determine the accessible item in a different ways.
The most general graph searches are concerned with both vertices and edges in the graph. For a general search, edges are stored in the dispenser. The following iterative algorithm searchs the vertices and edges of a graph that are reachable from the starting vertex s. If the algorithm is working with an undirected graph then the undirected edges are treated as pairs of directed edges, one in each direction.
visit s
while the dispenser is not empty
retrieve and remove edge e from the dispenser
let w be the head of e
if w has not been visited
do whatever you need to do with e (visit e)
visit w
endif
endwhile
In this algorithm, visiting a vertex w means doing the following:
do whatever you need to do with w
record that w has been visited
put the edges leaving w into the dispenser
Note that a vertex w can be visited at most once, and there is only one visited edge that has w as its head. This ensures that there is a only one path using visited edges from the starting vertex to a visited vertex. If the edge that takes you to vertex w is remembered for each vertex w, then you can reconstruct this path.
Some graph searches are primarily concerned with vertices in the graph. Then the above algorithm simplifies to the following.
visit s
while the dispenser is not empty
get vertex w from the dispenser
if w has not been visited
visit v
endif
endwhile
In this algorithm, visiting a vertex w means doing the following:
do whatever you need to do with w
record that w has been visited
put the neighbors of w into the dispenser
The order of visiting vertices or edges in a graph is determined by the type of dispenser that is used. A queue is used for breadth first searches, a stack is used for depth first searches, and a priority queue is used for priority first searches.
Breadth first searches have the useful property that they arrive at a vertex by the most direct route from the start vertex v. That is, when visit vertex w, you arrive through an edge on a path from v to w that has a minimal number of edges. If the edge that takes you to vertex w is remembered for each vertex w, then you can reconstruct a shortest path from v to any reachable vertex.
This idea can be modified to allow edges with different lengths by using a priority first search instead of a breadth first search. The priority of a vertex w is computed as the total distance from v to w, which is the length of the edge e that led to w plus the priority of the tail of e. This is the basis of one algorithm that finds all shortest paths and distances from a given start vertex.
Priority first searches are also the basis for algorithms for minimal spanning trees. A minimal spanning tree is a spanning tree whose length is as small as possible. The priority queue in a minimal spanning tree algorithm uses the length of an edge is used as its priority.
Graphs can capture any kind of binary relationship on a type of object. This leads to a number of variations in the graph search algorithm. Two of the major variations, visiting vertices and edges or just visiting vertices, have been described above. There is another variation that arises in exhaustive search contexts. These contexts are characterized by the following practical constraints:
For this kind of problem it is desirable to avoid using memory for edge objects but you still want to be able to recover information about paths from a start state to some objective state. This leads to an exhaustive search variant.
Avoiding using memory for edge objects necessitates using a variant of the algorithm that only visits vertices. Not visiting edges means you do not know the predecessor when you first arrive at a vertex unless you recorded that information when you arrived at its predecessor.
visit s from null
while the dispenser is not empty
get vertex u from the dispenser
if u has not been closed
visit the neighbors of u from u
endif
endwhile
In this algorithm, visiting a vertex requires recording that its neighbors can be reached from the vertex that you are currently visiting. So visiting v from u means doing the following:
record that v is closed
record that you get to v through u
record other needed information about v
add v to the dispenser