Graph traversal algorithms

There are many algorithms on graphs, which are based on a systematic enumeration of the vertices of the graph, such that each vertex is viewed (visited) exactly once. Therefore, an important task is to find good search methods in the graph.

By traversing graphs (search on graphs) we will mean the process of systematically viewing all the vertices of a graph in order to find vertices that satisfy a certain condition.

V.Lipsky calls the search method "good" if

• it allows the algorithm for solving the problem of interest to us to easily “immerse” in this method
• each edge of the graph is analyzed no more than once (or, which does not significantly change the situation, the number of times bounded by a constant).

This section presents the algorithm for traversing a graph, which is called Breadth First Search, and the tree corresponding to this algorithm. A Depth First Search algorithm is also presented and some properties of this type of traversal of the graph are proved.

These algorithms can be effectively used to search for vertices adjacent to a given vertex, build a simple path between two vertices, detect loops, check the graph for connectivity, and for many other problems.

Strategies for finding vertices on a graph.
(the vertices of the rib used during the search are marked in gray)