Breadth First Search (BFS)
BFS (breadth-first search, breadth-first search) - a graph traversal method, very often used in both simple and advanced algorithms. Breadth-First Search works by stepping through the individual levels of the graph, starting at the source node and gradually moving away from it. This is clearly shown in the animation.
To write the simplest BFS , you need to be able to work with a data structure that allows you to take from the beginning and put it to the end, and also be able to store the graph in the form of an adjacency list (i.e. with a queue ).
Formal description of the algorithm
1) Place the number of the vertex from which the search begins into the initially empty queue.
2) Extract the vertex U from the beginning of the queue and mark it as used in a separate array.
3) At the end of the queue, add all the vertices which we can reach using the edge from the vertex U, and which are not yet labeled.
4) If the queue is empty, then all nodes of the connected graph have been scanned, otherwise return to step 2.
Complexity
Since the algorithm visits all nodes of the graph in the worst case, when storing the graph as adjacency lists, time complexity of the algorithm is O(|V| + |E|), where V is the set of graph vertices, and E is the set of edges. In other words, the algorithm works in the worst case for number of edges + number of vertices.
|
BFS (breadth-first search) is a graph traversal method, very often used in both simple and advanced algorithms. Breadth-First Search works by stepping through the individual levels of the graph, starting at the source node and gradually moving away from it. This is clearly shown in the animation.
To write a simple BFS, you need to be able to work with a queue, a data structure that allows you to take from the beginning and put it to the end, and also be able to store a graph in the form of an adjacency list.
Formal description of the algorithm
1) Place the number of the vertex from which the search begins into the initially empty queue.
2) Extract vertex U from the beginning of the queue and mark it as used in a separate array.
3) At the end of the queue, add all the vertices that we can reach using the edge from the vertex U and that are not marked yet.
4) If the queue is empty, then all nodes of the connected graph have been scanned, otherwise return to step 2.
Difficulty of work
Since, in the worst case, the algorithm visits all nodes of the graph, when storing the graph in the form of adjacency lists, the time complexity of the algorithm is O(|V| + |E|), where V is the set of vertices of the graph, and E is the set of edges. ;
In other words, the algorithm works in the worst case for the number of edges + the number of vertices.
|
To restore shortest paths, create an array of "ancestors" \(p[]\), in which, for each vertex, store the number of the vertex by which we hit this vertex.
|