Построение логической и физической информационной модели (компьютерной). Физический уровень информационной модели
Реализация алгоритма без вычислительной системы
Поиск в ширину подобен обследованию лабиринта, когда от каждой вершины веерообразно обследуется каждый коридор.
Пример реализации процесса обхода графа в ширину для графа:
1 – начало обхода
Пример графа и способ обхода вершин в ширину
Итак, искомый порядок обхода в ширину: 1, 0, 2, 3, 4, 9, 5, 8, 6, 7. Извлеченные из очереди вершины записываются в начале каждой строки, а каждая строка содержит смежные и не посещенные вершины с заданной, помещаемые в очередь.
Динамика процесса поиска наглядно представляется деревом (лесом поиска для случая несвязного графа), в котором каждая вершина соответствует вершине графа, корень – началу поиска, а ребра – ребрам графа. Обход дерева в соответствии с уровнями от корня к листьям и слева направо представляет собой обход в ширину BFS.
Рис. 5. Дерево поиска в ширину BFS для графа рис. 4.
Свойство. Кратчайший путь из вершины v в w соответствующего графа находится как путь в дереве BFS с корнем в вершине v к вершине w.
Например, путь из вершины 1 в вершину 8 имеет кратчайшую длину равную 3, а последовательность вершин пути: 1- 0 - 9 - 8. Для графа, представленного на рис. 1, из 1 в 8 вершину существует другой путь 1 – 2 –5 – 8, однако, его длина также равна 3.
Хранение порядка обхода вершин по уровням в дереве BFS обеспечивается очередью.
Рис. 6. Состояние Очереди для вершин графа рис.4.
Рассмотрим представление структуры данных Очередь. Принцип работы Очереди соответствует «первым пришел, первым обслужен» (FIFO queue – First In First Out). Очередь может хранить информацию о посещенных вершинах или о ребрах, которые соединяют посещенные вершины с непосещенными.
Реализация алгоритма на вычислительной системе (с помощью системы программирования TurboPascal)
Выполним программную реализацию описанного выше алгоритма поиска в ширину на языке TurboPascal с учетом выбора структуры данных, отображающей граф конкретного вида, например, изображенного на рис. 4.
Граф представлен матрицей смежности C[i, j], каждый элемент которой индексирован номерами вершин и содержит значение C[i, j] = 1 для смежных вершин i и j, C[i ,j] = 0 для несмежных вершин.
Для представления Очереди в Паскале используем одномерный массив Q[i], обеспечивающий хранение элементов в порядке их поступления и извлечение в том же порядке. Начало и конец очереди запомним в переменных Un – указатель начала очереди, Uk – указатель конца очереди. Очередь поддерживает операции установки элемента в очередь (setQueue), извлечения элемента из очереди (getQueue), инициализации очереди (initQueue). Запишем программную реализацию этих процедур.
Procedure setQueue (v: integer);
Begin
Inc(Uk); Q[Uk]:=v;
End;
Procedure getQueue (var v: integer);
Begin
v:=Q[Un]; Inc(Un);
End;
Procedure initQueue;
Begin
Uk:=0; Un:=0;
End;
Посещенные и добавленные в очередь вершины отметим специальной меткой, в случае повторного нахождения данной отмеченной вершины как смежной с некоторой текущей вершиной поиска, отмеченную вершину не будем включать в очередь повторно. Таким образом, размер очереди ограничивается количеством вершин графа. Отмеченные вершины будем хранить в массиве Visit [i], индекс массива соответствует номеру вершины, а элемент – метка (например, true – непосещенные вершины, false – отмечены как посещенные).
program Poisk_v_shirinu;
const n=9; {количество вершин графа}
{представление графа матрицей смежности }
C: array [0..n,0..n] of 0..1=((0,1,0,0,0,0,0,0,0,1),
(1,0,1,1,1,0,0,0,0,0),
(0,1,0,0,0,1,0,0,0,0),
(0,1,0,0,1,0,0,0,0,0),
(0,1,0,1,0,0,0,0,0,0),
(0,0,1,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,0,0,0,1,0),
(0,0,0,0,0,1,1,1,0,1),
(1,0,0,0,0,0,0,0,1,0));
Visit: array [0..n] of boolean =(true,true,true,true,true,true,
true,true,true,true);
{вершины не посещались}
var v: integer; {вершина начала поиска}
procedure BFS( v:integer);
var Q: array [1..(n+1)] of 0..n;
{очередь представлена в виде массива}
Un,Uk: integer;
{с двумя указателями на начало и конец очереди}
j: integer;
begin
Un:=0; Uk:=0; {инициализация, очередь пуста}
Uk:=Uk+1; Q[Uk]:=v; {занести вершину в очередь}
{отметить вершину как посещенную}
Visit[v]:=false;
while Un < Uk do {пока очередь не пуста}
begin
{извлекаем элемент из очереди}
Un:=Un+1; v:=Q[Un];
{выводим элемент в порядке обхода в ширину}
write(v:3);
{просмотр всех вершин, связанных с v дугой}
for j:=0 to n do
if (C[v,j]=1) and (Visit[j]) then
begin
{если вершина ранее не посещалась и связана дугой, то заносим в очередь}
Uk:=Uk+1; Q[Uk]:=j;
{отмечаем как посещенную вершину}
Visit[j]:=false;
end;
end; {while}
end; {procedure}
begin
writeln('Поиск в ширину');
writeln (‘Введите вершину начала поиска’); readln(v);
BFS(v); { поиск в ширину от исходной вершины v}
end.
Практическая работа
Упражнения
Задание 1: Выполните обход в ширину для графа, изображенного на рис. 4, не используя программную реализацию. Начало обхода совпадает с вершиной 8. Запишите полученный список вершин.
Задание 2: Выполните программную реализацию обхода графа в ширину. Исследуйте механизм обхода на примерах различных графов.
Задание 3: Модифицируйте приведенный пример программной реализации поиска на графе в ширину, запишите программу с использованием основных операций структуры данных Очередь.
Задачи:
Часть 1.
· Постройте реализацию поиска в ширину, которая использует очередь, состоящую из ребер графа. Граф представлен матрицей смежности.
· Постройте реализацию поиска в ширину с использованием очереди ребер графа. Граф представляется списком смежных вершин. (Для хранения списка смежных вершин используйте двумерный массив или два одномерных массива, индексированных номером ребра)
· Решите задачу 2 для случая представления графа списком смежных вершин с использованием динамических структур данных, например массива указателей на связанный список.
· Напишите программу нахождения кратчайшего пути в графе из вершины v в w с использованием процесса поиска в ширину. Дерево поиска BFS представлено в виде родительских связей (массив, индексированный номерами вершин и содержащий элементы – родительскую вершину). Программа распечатывает кратчайший путь (в виде последовательности вершин найденного пути) из заданной вершины v к любой из вершин. Используйте представление графа в виде матрицы смежности.
· Решите задачу 4 для представления графа списком смежных вершин. Для представления графа используйте массивы.
· Решите задачу 4 для представления графа списком смежных вершин. Для представления графа используйте динамические структуры данных, массив указателей на связанный список.
· Напишите программу, реализующую нахождение длины кратчайшего пути от одной вершины – источника ко всем остальным вершинам графа с применением метода поиска в ширину. Используйте представление графа в виде матрицы смежности.
· Разработайте и напишите программу нахождения длины пути, достаточного, чтобы связать между собой любую пару вершин. Данная величина называется диаметром графа (Уточните случай, когда граф оказывается несвязным).
· Разработайте и напишите программу нахождения высоты дерева поиска в ширину BFS (высота дерева определяется как длина пути от корня к самому удаленному листу).
Часть 2
1. Разработайте программную реализацию построения случайного графа и графического изображения его на плоскости. Выполните нахождение обхода графа в ширину и построение графической визуализации динамики разворачивающегося поиска.
Процесс прохождения вершин визуально отобразите, например сменой цвета вершины и закрашиванием соответствующих ребер с задержкой по времени, задаваемой фиксированной константой в миллисекундах или реализуемой по внешнему событию со стороны пользователя, например щелчок по кнопке. Используйте для реализации визуальные среды программирования (Visual Basic, Delphi).
2. Разработайте программную реализацию построения случайного графа и графического изображения его на плоскости. Выполните нахождение обхода графа в ширину и построение графической визуализации динамики разворачивающегося поиска кратчайшего пути между парой вершин v и w. Кратчайший путь визуально отобразите сменой цвета соответствующих ребер. Программа должна позволять задавать произвольные значения вершинам начала и конца пути. Используйте для реализации визуальные среды программирования (Visual Basic, Delphi).
3. Разработайте программную реализацию построения случайного графа и графического изображения его на плоскости. Выполните нахождение дерева BFS, соответствующего обходу графа в ширину и построение графической визуализации дерева. Кратчайший путь от вершины источника – вершины дерева визуально отобразите сменой цвета соответствующих ребер. Программа должна позволять задавать произвольные значения вершине начала пути обхода.
Используйте для реализации визуальные среды программирования (Visual Basic, Delphi).