Поиск в ширину (обход по уровням). Теория графов.

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

Пусть задан граф 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++:

C++

#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:

Delphi/Pascal

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 имеющихся вершин (программы не предусматривают некорректных входных данных):

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

#include «stdafx.h»
#include <iostream>
#include <windows.h>
using namespace std;
void gotoxy(int x, int y) //в Windows
{
COORD k;
HANDLE hOuput = GetStdHandle(STD_OUTPUT_HANDLE);
k.X=x; k.Y = y;
SetConsoleCursorPosition(hOuput, k);
}
void fun_symbol(int _x, int _y, int sh, int v)
{
int j, i; char mas[255][255];
for (i=0; i<v; i++)
{gotoxy(_x, _y);
mas[i][i]=176; cout<<mas[i][i];
for (j=1; j<sh—1; j++)
{
if (i==0 || i==(v—1))
{mas[i][j]=176;
cout<<mas[i][j];}
else cout<<» «;
}
mas[i][j]=176; cout<<mas[i][j];
cout<<endl; _y++;
}}
int main()
{SetConsoleCP(1251); SetConsoleOutputCP(1251);
int sh, v, x, y;
cout<<» Введите координату x >> «; cin>>x;
cout<<» Введите координату y >> «; cin>>y;
cout<<» Введите ширину >> «; cin>>sh;
cout<<» Введите высоту >> «; cin>>v;
system(«cls»);
fun_symbol(x, y, sh, v);
system(«pause>>void»);
return 0;
}

C++. Функции. Задача 10

Написать функцию, специализированную на вывод строки из звездочек, количество которых определяется пользователем.

Решение:

АВЛ-дерево.

АВЛ-дерево – структура данных, изобретенная в 1968 году двумя советскими математиками: Евгением Михайловичем Ландисом и Георгием Максимовичем Адельсон-Вельским. Прежде чем дать конструктивное определение АВЛ-дереву, сделаем это для сбалансированного двоичного дерева поиска.

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

АВЛ-дерево – сбалансированное двоичное дерево поиска с k=1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor – это разность высот правого и левого поддеревьев, принимающая одно значение из множества {-1, 0, 1}. Ниже изображен пример АВЛ-дерева, каждому узлу которого поставлен в соответствие его реальный коэффициент сбалансированности.

Пример АВЛ-дерева

Положим B_i – коэффициент сбалансированности узла T_i (i – номер узла, отсчитываемый сверху вниз от корневого узла по уровням слева направо). Balance factor узла T_i рассчитывается следующим образом. Пусть функция h() с параметрами T_iи L возвращает высоту левого поддерева L узла T_i, а с T_i и R – правого. Тогда B_i=h(T_i, R)-h(T_i, L). Например, B₄=-1, так как h(T₄, R)-h(T₄, L)=0-1=-1.

Сбалансированное дерево эффективно в обработке, что следует из следующих рассуждений. Максимальное количество шагов, которое может потребоваться для обнаружения нужного узла, равно количеству уровней самого бинарного дерева поиска. А так как поддеревья сбалансированного дерева, «растущие» из произвольного корня, практически симметричны, то и его листья расположены на сравнительно невысоком уровне, т. е. высота дерева сводиться к оптимальному минимуму. Поэтому критерий баланса положительно сказывается на общей производительности. Но в процессе обработки АВЛ-дерева, балансировка может нарушиться, тогда потребуется осуществить операцию балансировки. Помимо нее, над АВЛ-деревом определены операции вставки и удаления элемента. Именно выполнение последних может привести к дисбалансу дерева.

Доказано, что высота АВЛ-дерева, имеющего N узлов, примерно равна log₂N. Беря в виду это, а также то, то, что время выполнения операций добавления и удаления напрямую зависит от операции поиска, получим временную сложность трех операций для худшего и среднего случая – O(logN).

Прежде чем рассматривать основные операции над АВЛ-деревом, определим структуру для представления его узлов, а также три специальные функции:

struct Node { int key; char height; Node *right; Node *left; Node(int k) { key=k; height=1; left=right=0; } }; char height(Node *p) { if (p) return p->height; else return 0; } int BF(Node *p) { return height(p->right)-height(p->left); } void OverHeight(Node *p) { char hleft=height(p->left); char hright=height(p->right); p->height=(hleft>hright? hleft: hright)+1; }

Структура Node описывает узлы АВЛ-дерева. Ее поля right и left являются указателями на правое и левое поддеревья. Поле key хранит ключ узла, height – высоту поддерева. Функция-конструктор создает новый узел. Функции height и BF вычисляют коэффициент сбалансированности узла, а OverHeight – корректирует значение поля height, затронутое в процессе балансировки.

Балансировка.

Если после выполнения операции добавления или удаления, коэффициент сбалансированности какого-либо узла АВЛ-дерева становиться равен 2, т. е. |h(T_i, R)-h(T_i, L)|=2, то необходимо выполнить операцию балансировки. Она осуществляется путем вращения (поворота) узлов – изменения связей в поддереве. Вращения не меняют свойств бинарного дерева поиска, и выполняются за константное время. Всего различают 4 их типа:

1. малое правое вращение;
2. большое правое вращение;
3. малое левое вращение;
4. большое левое вращение.