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.

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.

visitswhile the dispenser is not empty retrieve and remove edgeefrom the dispenser letwbe the head ofeifwhas not been visited do whatever you need to do withe(visite) visitwendif endwhile

In this algorithm, visiting a vertex **w** means doing the following:

do whatever you need to do withwrecord thatwhas been visited put the edges leavingwinto 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.

visitswhile the dispenser is not empty get vertexwfrom the dispenser ifwhas not been visited visitvendif endwhile

In this algorithm, visiting a vertex **w** means doing the following:

do whatever you need to do withwrecord thatwhas been visited put the neighbors ofwinto 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:

- The graph is huge, often the state space of some complex problem. The edges are typically allowed transitions between states.
- It is impractical to construct the entire graph, but it is easy to navigate it locally. That is, given a state you can easily determine its adjacent states — states that can be reached from the given state by a single transition.

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**.

visitsfrom null while the dispenser is not empty get vertexufrom the dispenser ifuhas not been closed visit the neighbors ofufromuendif 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 thatvis closed record that you get tovthroughurecord other needed information aboutvaddvto the dispenser