You get a bonus - 1 coin for daily activity. Now you have 1 coin

Graph traversal algorithms

Lecture




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.

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


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms