Lecture
Breadth-first search (level-by-level traversal) is one of the algorithms for traversing a graph. The method underlies several other algorithms of a similar nature. Breadth-first search involves examining the graph level by level: first the root – an arbitrarily chosen node – is visited, then all children of that node, after which the children of the children are visited, and so on. Vertices are examined in order of increasing distance from the root.
Let a graph G=(V, E) and a root s, from which the traversal begins, be given. After visiting node s, the nodes adjacent to s will be visited next (let us denote the set of nodes adjacent to s as q; it is obvious that q⊆V, that is, q is some subset of V). Next, this procedure is repeated for the vertices adjacent to the vertices in the set q, with the exception of vertex s, since it has already been visited. Thus, continuing to traverse level by level, the algorithm will visit all vertices of the set V reachable from s. The algorithm terminates after traversing all vertices of the graph, or when some existing condition is met.
Considering the following example, let us assume that during the operation of the algorithm each vertex of the graph can be colored one of three colors: black, white, or gray. Initially all vertices are white. During the traversal, each vertex, as it is discovered, is first colored gray and then black. A particular moment of the traversal is described by the following condition: if a vertex is black, then all of its children are colored gray or black.
We have a mixed graph (see figure) with |V| = 4 and |E| = 5. Let us traverse its vertices using the breadth-first search algorithm. We take node 3 as the starting vertex. First it is marked gray as discovered, and then black, since the nodes adjacent to it (1 and 4) are discovered, which, in turn, are marked gray in that order. Next, node 1 is colored black, and its neighbor – node 2 – is found, which becomes gray. And finally, nodes 4 and 2, in that order, are examined, and the breadth-first traversal is complete.
The breadth-first search algorithm works on both directed and undirected graphs. The mixed graph used in the example was intended to illustrate this. It should be noted that in an undirected connected graph this method will traverse all existing nodes, whereas in a mixed graph or digraph this is not necessarily the case. Moreover, up to this point we have considered a traversal of all vertices, but it is quite possible that, for example, examining a certain number of them, or finding a specific vertex, would be sufficient. In such a case the algorithm will have to be adapted somewhat, rather than being changed completely or abandoned altogether.
Now let us move on to a more formal description of the breadth-first search algorithm. The main objects – three data structures used in the program – will be:
The first two structures have an integer data type, the last a boolean one. Visited vertices are recorded in the visited array, which prevents looping, while the queue will store the nodes involved. Recall that the «queue» data structure operates on the «first in, first out» principle. Let us consider the graph traversal process broken down into stages:
Breadth-first search, starting from the starting vertex, gradually moves further and further away from it, passing level by level. It turns out that by the end of the algorithm's operation, all shortest paths from the starting vertex to each node reachable from it will have been found.
To implement the algorithm in a programming language, one needs the ability to define a graph programmatically, as well as an understanding of a data structure such as a queue.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include "stdafx.h"
#include using namespace std; const int n=4; int i, j; //graph adjacency matrix int GM[n][n] = { {0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1}, {0, 1, 0, 0} }; //breadth-first search void BFS(bool *visited, int unit) { int *queue=new int[n]; int count, head; for (i=0; icount=0; head=0; queue[count++]=unit; visited[unit]=true; while (head{ unit=queue[head++]; cout< |
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
program BreadthFirstSearch;
uses crt; const n=4; type MassivInt=array[1..n, 1..n] of integer; MassivBool=array[1..n] of boolean; var i, j, start: integer; visited: MassivBool; {graph adjacency matrix} const GM: MassivInt = ( (0, 1, 1, 0), (0, 0, 1, 1), (1, 0, 0, 1), (0, 1, 0, 0)); {breadth-first search} procedure BFS(visited: MassivBool; _unit: integer); var queue: array[1..n] of integer; count, head: integer; begin for i:=1 to n do queue[i]:=0; count:=0; head:=0; count:=count+1; queue[count]:=_unit; visited[_unit]:=true; while headbegin head:=head+1; _unit:=queue[head]; write(_unit, ' '); for i:=1 to n do begin if (GM[_unit, i]<>0) and (not visited[i]) then begin count:=count+1; queue[count]:=i; visited[i]:=true; end; end; end; end; {main program block} begin clrscr; write('Starting vertex >> '); read(start); writeln('Graph adjacency matrix: '); for i:=1 to n do begin visited[i]:=false; for j:=1 to n do write(' ', GM[i, j]); writeln; end; write('Traversal order: '); BFS(visited, start); end. |
These two programs use the graph shown in the previous figure, or more precisely its adjacency matrix. Only one of 4 values can be entered, since only one of the 4 existing vertices can be specified as the starting one (the programs do not account for invalid input data):
| Input data | Output data |
| 1 | 1 2 3 4 |
| 2 | 2 3 4 1 |
| 3 | 3 1 4 2 |
| 4 | 4 2 3 1 |
The graph is represented by an adjacency matrix, and in terms of efficiency this is not the best option, since the time spent traversing it is estimated at O(|V|2), whereas it can be reduced to O(|V|+|E|) by using an adjacency list.
Comments