4. Задача №4.34
4.1. Постановка задачи и ее анализ
Выполнить обход в ширину неориентированного графа, начиная с заданной вершины. Способ представления графа – матрица смежности.
4.2. Описание структур данных
N:integer; //количество элементов
a:array [1 .. 100, 1 .. 100] of integer; //тип матрицы смежности, М [i,j]>0, если существует ребро, идущее от вершины i к j
i,j :integer;
visit: array [ 1 .. 100 ] of boolean;//массив посещения вершин
flag: boolean;
4.3. Проектирование программы
Способ предоставления графа в моей задаче – матрица смежности. Я создала двумерный массив a:array [1 .. 100, 1 .. 100] of integer. В матрице а[i,j]=1 (или больше, если граф взвешенный, то есть каждое ребро имеет свой вес или стоимость), если существует ребро между вершинами i и j, или a[i,j]=0, если такого ребра нет. Суть алгоритма обхода графа в ширину заключается в том, чтобы перебрать всех преемников начальной вершины (корневого узла) и дальше по цепочке, то есть рассмотреть все вершины, связанные с текущей. Для реализации необходимо воспользоваться структурой данных очередь.
Такой алгоритм помогает получить компоненту связности, то есть схему, куда можно прийти из какой-то заданной вершины. В моей программе пользователь сам определяет вершину, с которой нужно начинать обход.
Рассмотрим подробнее алгоритм поиска вершин, по которым можно обойти граф:
writeln ('Введите вершину, с которой хотите начать обход:');
readln (v); // начинаем обход с вершины v
visit[v]:=true; // вершина v посещена
st:=0; //начальная инициализация
en:=0; // начальная инициализация
while st<=en do //пока очередь не пуста
begin
for i:=1 to N do begin
if (a[v,i]=1) and (not visit[i]) then //если можем добраться до вершины, и она не посещена
begin
inc(en);
q[en]:=i;
visit[i]:=true;
end;
end;
// удаляем вершину из очереди и обрабатываем следующую
inc (st);
v:=q[st];
end;
4.4. Результаты отладки и тестирования программы.
При запуске программы пользователю предлагается ввести количество вершин, а также значения вершин, между которыми есть связи. Таким образом, мы составляем матрицу смежности (рис. 4.1.):
Рис. 4.1. – Создание матрицы смежности
После этого пользователь должен ввести вершину, с которой он хочет начать обход. Программа выдаст вершины, до которых можно добраться из заданной (рис. 4.2.):
Рис 4.2. – Результат программы
Список использованных источников
В.Н.Касьянов, В.А.Евстигнеев «Графы в программировании: обработка, визуализация и применение» СПб. БХВ-Петербург, 2003.
С.Окулов «Программирование в алгоритмах» М.:БИНОМ. Лаборатория знаний, 2004.