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. In a stack, it is the item that was inserted last. In a queue, it is the item that was inserted first. In a priority queue, it is the item that has the highest priority. The priority of an item in a priority queue may be specified as a parameter when the item is inserted, or it may be determined from the item's data contents. For some algorithms, it is useful to use random dispensers. A random dispenser uses a randomized algorithm to determine the accessible item.

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 *v*.
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 v 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 means doing the following:

do whatever you need to do with v record that v has been visited put the edges leaving v 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 v 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 means doing the following:

do whatever you need to do with v record that v has been visited put the neighbors of v 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.

Section overview text.