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
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.
|
Comments
To leave a comment
Algorithms
Terms: Algorithms