Counts for the smallest: BFS
In the previous post, it was told about traversing the graph in depth. Today I would like to tell you about a no less important algorithm of graph theory - about a wide bypass.
Last time, we learned to look for some way through the maze. Anyone wishing to find the shortest path please under the cat.
Intuitively, we would like to consider the graph vertices in the order of increasing the distance from the original one, as shown in the figure.
Divide all vertices into three sets:
Obviously, as soon as all the vertices are black, the work of the algorithm is completed. We will store all gray vertices in the queue and maintain the following property: the distances to all gray vertices in the order in which they lie in the queue do not monotonously decrease.
We get the first vertex from the queue (we denote it by v). For each of its neighbors, w, one of two options is possible:
Repeat as long as there is at least one gray vertex.
Evidence:
The maximum number of vertices simultaneously stored in the queue is V, that is, the maximum amount of memory used is O (V).
')
Next time I will try to consider a more complex task based on our favorite maze and, in her example, tell Dijkstra's algorithm.
Last time, we learned to look for some way through the maze. Anyone wishing to find the shortest path please under the cat.
Formulation of the problem
It is required to find a path from one vertex of the graph to another, and the path must be minimal in the number of edges.Algorithm Description
Intuitively, we would like to consider the graph vertices in the order of increasing the distance from the original one, as shown in the figure.
Divide all vertices into three sets:
- Fully machined vertices (initially the set is empty, shown in black in the figure)
- Vertices to which the distance is known (initially there is only one vertex in the set — the initial one, shown in gray in the figure)
- Vertices, about which nothing is known (initially - all vertices, except the initial one, are marked in white in the figure)
Obviously, as soon as all the vertices are black, the work of the algorithm is completed. We will store all gray vertices in the queue and maintain the following property: the distances to all gray vertices in the order in which they lie in the queue do not monotonously decrease.
We get the first vertex from the queue (we denote it by v). For each of its neighbors, w, one of two options is possible:
- w - black or gray top. In this case, we do not receive any new information.
- w - white top. Then the distance to it is d (w) = d (v) + 1. And, since we learned the distance, w becomes a gray vertex
Repeat as long as there is at least one gray vertex.
Implementation
It is assumed that the graph is stored in an array of vector <vector <int >> edges, and edges [v] contains the numbers of all the vertices to which there is an edge from v. It is also assumed that the global variable start contains the number of the initial vertex.Bfs
void BFS() { queue<int> q; // : q.push(start); d[start] = 0; mark[start] = 1; // - while (!q.empty()) { // int v = q.front(); q.pop(); // for (int i = 0; i < (int)edges[v].size(); ++i) { // if (mark[edges[v][i]] == 0) { // d[edges[v][i]] = d[v] + 1; // mark[edges[v][i]] = 1; q.push(edges[v][i]); } } } } Why does this work?
Consider any vertex v reachable from the initial one. Let p [0] = start, p [1], ..., p [k] = v be the shortest path from the initial vertex to the vertex v. Then the resulting value of the algorithm d [v] = k.Evidence:
- d [v] ≤ k
- Base: vertex p [0] = start is visited by the algorithm, and d [p [0]] = 0
- Assumption: the vertex p [i - 1] is visited by the algorithm, with d [p [i]] ≤ i
- Step: when considering the vertex p [i - 1] (and perhaps earlier), the edge leading to the vertex p [i] will be considered. Thus, d [p [i]] ≤ i
- d [v] ≥ k
Suppose that d [v] <k. Consider the vertex v; that vertex, when considering which the vertex v was colored gray (we denote it by w); that vertex, on consideration of which vertex w was colored gray; ...; start start. Every two adjacent vertices in this sequence are connected by an edge according to the construction of the algorithm. Thus, we found a path from the start vertex to the vertex v of length less than k — a contradiction, therefore, d [v] ≥ k
Algorithm complexity
For each edge and each vertex, the algorithm performs a constant number of actions, therefore, the time complexity is O (V + E).The maximum number of vertices simultaneously stored in the queue is V, that is, the maximum amount of memory used is O (V).
')
Instead of conclusion
In this article, we found the shortest path through the maze using one of the most well-known graph theory algorithms - BFS.Next time I will try to consider a more complex task based on our favorite maze and, in her example, tell Dijkstra's algorithm.
Source: https://habr.com/ru/post/200252/
All Articles