«

»

Поиск в ширину

Поиск в ширину (обход по уровням) – один из алгоритмов обхода графа.  Метод лежит в основе некоторых других алгоритмов близкой тематики. Поиск в ширину подразумевает поуровневое исследование графа: вначале посещается корень – произвольно выбранный узел, затем – все потомки данного узла, после этого посещаются потомки потомков и т.д. Вершины просматриваются в порядке возрастания их расстояния от корня.

Пусть задан граф G=(V, E) и корень s, с которого начинается обход. После посещения узла s, следующими за ним будут посещены смежные с s узлы (множество смежных с s узлов обозначим как q; очевидно, что q⊆V, то есть q – некоторое подмножество V). Далее, эта процедура повториться для вершин смежных с вершинами из множества q, за исключением вершины s, т. к. она уже была посещена. Так, продолжая обходить уровень за уровнем, алгоритм обойдет все доступные из s вершины множества V. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения наличествующего условия.

Рассматривая следующий пример, будем считать, что в процессе работы алгоритма каждая из вершин графа может быть окрашена в один из трех цветов: черный, белый или серый. Изначально все вершины белые. В процессе обхода каждая из вершин, по мере обнаружения, окрашивается сначала в серый, а затем в черный цвет. Определенный момент обхода описывает следующие условие: если вершина черная, то все ее потомки окрашены в серый или черный цвет.

 

Поиск в ширину

 

Имеем смешанный граф (см. рис.) с |V| = 4 и |E| = 5. Выполним обход его вершин, используя алгоритм поиска в ширину. В качестве стартовой вершины возьмем узел 3. Сначала он помечается серым как обнаруженный, а затем черным, поскольку обнаружены смежные с ним узлы (1 и 4), которые, в свою очередь, в указанном порядке помечаются серым. Следующим в черный окрашивается узел 1, и находятся его соседи – узел 2, который становится серым. И, наконец, узлы 4 и 2, в данном порядке, просматриваются, обход в ширину завершается.

Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах. Дать понять это был призван смешанный граф, используемый в примере. Стоит отметить, в неориентированном связном графе данный метод обойдет все имеющиеся узлы, а в смешанном или орграфе это необязательно произойдет. К тому же, до сих пор рассматривался обход всех вершин, но вполне вероятно, достаточным окажется, например просмотр определенного их количества, либо нахождение конкретной вершины. В таком случае придется немного приспособить алгоритм, а не изменять его полностью или вовсе отказаться от использования такового.

Теперь перейдем к более формальному описанию алгоритма поиска в ширину. Основными объектами – тремя структурами данных, задействованными в программе, будут:

  • матрица смежности графа GM;
  • очередь queue;
  • массив посещенных вершин visited.

Две первые структуры имеют целочисленный тип данных, последняя – логический. Посещенные вершины, заносятся в массив visited, что предотвратит зацикливание, а очередь queue будет хранить задействованные узлы. Напомним, что структура данных «очередь» работает по принципу «первый пришел – первый вышел». Рассмотрим разбитый на этапы процесс обхода графа:

  1. массив visited обнуляется, т. е. ни одна вершина графа еще не была посещена;
  2. в качестве стартовой, выбирается некоторая вершина s и помещается в очередь (в массив queue);
  3. вершина s исследуется (помечается как посещенная), и все смежные с ней вершины помещаются в конец очереди, а сама она удаляется;
  4. если на данном этапе очередь оказывается пустой, то алгоритм прекращает свою работу; иначе посещается вершина, стоящая в начале очереди, помечается как посещенная, и все ее потомки заносятся в конец очереди;
  5. пункт 4 выполняется пока это возможно.

Поиск в ширину, начиная со стартовой вершины, постепенно уходит от нее все дальше и дальше, проходя уровень за уровнем. Получается, что по окончанию работы алгоритма будут найдены все кратчайшие пути из начальной вершины до каждого доступного из нее узла.

Для реализации алгоритма на ЯП потребуется: умение программно задавать граф, а также иметь представление о такой структуре данных, как очередь.

Код программы на C++:

 

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 <iostream>
using namespace std;
const int n=4;
int i, j;
//матрица смежности графа
int GM[n][n] =
{
{0, 1, 1, 0},
{0, 0, 1, 1},
{1, 0, 0, 1},
{0, 1, 0, 0}
};
//поиск в ширину
void BFS(bool *visited, int unit)
{
int *queue=new int[n];
int count, head;
for (i=0; i<n; i++) queue[i]=0;
count=0; head=0;
queue[count++]=unit;
visited[unit]=true;
while (head<count)
{
unit=queue[head++];
cout<<unit+1<<" ";
for (i=0; i<n; i++)
if (GM[unit][i] && !visited[i])
{
queue[count++]=i;
visited[i]=true;
}
}
delete []queue;
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
int start;
cout<<"Стартовая вершина >> "; cin>>start;
bool *visited=new bool[n];
cout<<"Матрица смежности графа: "<<endl;
for (i=0; i<n; i++)
{
visited[i]=false;
for (j=0; j<n; j++)
cout<<" "<<GM[i][j];
cout<<endl;
}
cout<<"Порядок обхода: ";
BFS(visited, start-1);
delete []visited;
system("pause>>void");
}

 

Код программы на Pascal:

 

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;
{матрица смежности графа}
const GM: MassivInt = (
(0, 1, 1, 0),
(0, 0, 1, 1),
(1, 0, 0, 1),
(0, 1, 0, 0));
{поиск в ширину}
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 head<count do
begin
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;
{основной блок программы}
begin
clrscr;
write('Стартовая вершина >> '); read(start);
writeln('Матрица смежности графа: ');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(' ', GM[i, j]);
writeln;
end;
write('Порядок обхода: ');
BFS(visited, start);
end.

 

В двух этих программах используется граф, изображенный на предыдущем рисунке, точнее его матрица смежности. На ввод может поддаваться только одно из 4 значений, т. к. в качестве стартовой возможно указать лишь одну из 4 имеющихся вершин (программы не предусматривают некорректных входных данных):

 

Входные данные Выходные данные
1 1 2 3 4
2 2 3 4 1
3 3 1 4 2
4 4 2 3 1

 

Граф представлен матрицей смежности, и относительно эффективности это не самый лучший вариант, так как время, затраченное на ее обход, оценивается в O(|V|2), а сократить его можно до O(|V|+|E|), используя список смежности.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *