Databases Reference
In-Depth Information
Though we've used depth-first search as our underlying strategy for general graph tra‐
versals, many interesting “higher-order” algorithms traverse the entire graph in a
breadth-first
manner. That is, they explore the graph one layer at a time, first visiting
each node at depth 1 from the start node, then each of those at depth 2, then depth 3,
and so on, until the entire graph has been visited. This progression is easily visualized
starting at the node labelled
O
(for
origin
) and progressing outward a layer at a time, as
shown in
Figure 7-1
.
Figure 7-1. The progression of a breadth-first search
The termination of the search depends on the algorithm being executed—most useful
algorithms aren't pure breadth-first search but are informed to some extent. Breadth-
first search is often used in path-finding algorithms or when the entire graph needs to
be systematically searched (for the likes of
graph global
algorithms we discussed in
Chapter 3
).
Path-Finding with Dijkstra's Algorithm
Breadth-first search underpins numerous classical graph algorithms, including Dijk‐
stra's algorithm. Dijkstra (as it is often abbreviated) is used to find the shortest path
between two nodes in a graph. Dijkstra's algorithm is mature, having been published in
1956, and thereafter widely studied and optimized by computer scientists. It behaves as
follows:
