по дисциплине «Теория алгоритмов»
Выполнил: ст-т гр. 20КП01
Климочкин Д.Ю., Танин М.В.
Проверил: доцент каф. ИВС
Дрождин В.В.
1 Формулировка задачи
Для неориентированного графа G с вершинами vi Î V (| V | ≤ 80) и ребрами ek Î E (| E | ≤ 150) подсчитать количество компонентов связности и количество петель.
Граф G задается списком вершин и списком ребер.
2 Техническое задание
2.1 Требования к программе
Программа должна вводить граф G из текстового файла: в первой строке содержатся n и m, во второй строке – список из n вершин, а в последующих m строках – список ребер, в котором каждое ребро представлено парой инцидентных ему вершин.
По результатам анализа графа G программа должна подсчитать количество компонентов связности и количество петель.
2.2 Порядок контроля и приёмки
Для контроля правильности работы программы необходимо подготовить файл с исходными тестовыми данными и запустить программу на выполнение. По результатам анализа графа программа выдает сообщение о количестве компонентов связности и количестве петель. Если результат совпадет с тестовыми данными, то это означает, что программа работает корректно.
3 Описание программы
3.1 Общие сведения
Программа разработана в среде Pascal. Текст программы приведен в приложении А.
3.2 Функциональное назначение
Программа предназначена для анализа графа общего вида и подсчёт количество компонентов связности и количество петель.
3.3 Описание логической структуры
Решение задачи выполняется в несколько этапов:
1. Ввод исходных данных из текстового файла: количества вершин n и количества ребер m, списка из n вершин и списка из m ребер.
2. Сортировка списка ребер по возрастанию.
3. Подсчёт количества компонентов связности.
4. Подсчёт количества петель.
5. Вывод сообщений: количество компонентов связности и количество петель.
Граф общего вида в программе будем представлять совокупностью списков вершин a и ребер b.
В задаче требуется подсчитать количество компонентов связности и количество петель, значит нужно проанализировать список вершин.
Для более эффективной обработки ребер графа каждое ребро ek(vi, vj) перепишем так, чтобы vi ≤ vj (так как в неориентированном графе по ребру ek можно пройти от vi к vj и от vj к vi), и отсортируем список ребер методом пузырька по возрастанию.
Для подсчёта количества компонентов связности нужно построить граф и после построения будем подсчитывать компоненты связности. Если в построенном графе есть вершины, которые не входят в данный граф и эти вершины связанны между собой, то анализ графа прекращается и выдаётся сообщение о количестве компонентов связности.
Для подсчёта количества петель в графе будем строить граф и после построения, будем определять, есть ли ребро, которое входит в одну и ту же вершину. Как только такая вершина находится, то анализ графа прекращается и выдается сообщение о количестве петель.
Вывод сообщений о результатах анализа графа осуществляется следующим образом: после преобразования графа общего вида в граф выдается сообщение о количестве компонентов связности, а после выявления одинаковой вершины– выдается сообщение о количестве петель.
Алгоритм решения задачи на псевдокоде представлен на рисунке 1.
Начало
Данные:
n, m – целые // количество вершин и ребер в заданном графе
nv – целая // количество вершин вошедших в компоненты связности
mg – целая // количество обрабатываемых ребер
i, j, k,c – целые // внутренние переменные
а – массив [1..80] целых // список вершин
b – массив [1..150, 1..2] целых // список ребер
v – множество целых // множество вершин, входящих в компоненту связности
yes – логическая // признак наличия циклов в графе
yess – логическая // признак добавления вершин в компоненту связности
f – файловая переменная для текстового файла
Выполнить:
// Чтение заданного графа из файла '5 - input.txt'
открытие файла '5 - input.txt'
ввод из файла n, m
ввод из файла списка вершин v
вывод списка вершин v
ввод из файла списка ребер e
вывод списка ребер e
// Построение графа
для каждого r в t делать
k:= k + 1
вывести
закрыть(f)
пока m > 0
t:= [];
t:= t + [b[1, 1], b[1, 2]];
b[1, 1]:= b[m, 1];
b[1, 2]:= b[m, 2];
m:= m - 1;
yes:= true;
пока (m > 0) и yes
yes:= false
для i от 1 до m
если (b[i, 1] в t) или же (b[i, 2] в t) тогда
t:= t + [b[i, 1], b[i, 2]];
b[i, 1]:= b[m, 1];
b[i, 2]:= b[m, 2];
m:= m - 1;
yes:= true;
конец для
конец для
k:= k + 1
конец для
вывести 'Количество петель = '
вывести 'Количество компонентов связности = '
Конец.
Рисунок 1 – Алгоритм на псевдокоде
Текст программы в форме консольного приложения приведен в приложении А.
Программа реализует последовательное решение следующих задач:
1. Ввод исходных данных из текстового файла: количества вершин а и количества ребер b, списка v из a вершин и списка e из b ребер.
2. Поиск компонентов связности.
3. Поиск количества петель.
4. Вывод сообщений: количество компонентов связности и количество петель.
4 Программа и методика испытаний
Для проверки правильности работы программы подготовлен тестовый набор данных:
Исходные данные:
a = 9
b = 7
v = 1, 2, 3, 4, 5, 6, 7, 8, 9
e = 1, 2; 2, 3; 5, 4; 5, 3; 3, 3; 2, 1; 6, 7
Результат:
Количество петель = 1
Количество компонентов связности = 4
При проверке работы программы получены результаты, приведенные в приложении Б, в которых заданные исходные данные и результаты совпадают. Таким образом, можно сделать вывод, что программа работает корректно.
5 Описание применения
После запуска программы на выполнение система пытается открыть текстовый файл '5 - input.txt'. Если файл не найден, то выдается системная ошибка, иначе на экране появляются описание графа общего вида и результаты его анализа (см. Приложение Б).
Заключение
В ходе выполнения лабораторной работы разработано техническое задание на решение задачи, разработан алгоритм решения задачи, осуществляющий чтение описания графа общего вида из файла и его анализ, составлена и отлажена программа, и оформлена программная документация. Проведенные испытания показали, что программа работает корректно.
ТЕКСТ ПРОГРАММЫ
Приложение А
(обязательное)
Var
n, nv, m, mg, i, j, k, c: integer;
a: array [1..80] of integer; //вершины
b: array [1..150, 1..2] of integer; //рёбра
v: set of integer; // множество вершин, входящих в компоненту связности
yes: boolean; // признак наличия циклов в графе
yess: boolean; // признак добавления вершин в компоненту связности
f: text;
t: set of integer;
Begin
// Чтение заданного графа из файла '5 - input.txt'
writeln('Заданный граф общего вида');
assign(f, 'input.txt'); // Связывание переменной f с файлом на диске
reset(f); // Открытие файла
readln(f, n, m); // Чтение количества вершин n и количества ребер m из файла
writeln('Вершин = ', n, ' Ребер = ', m);
writeln('Вершины:');
for i:= 1 to n do
Begin
read(f, k); // Чтерие списка вершин из файла
t:= t + [k];
write(k, ' ');
end;
writeln;
writeln('Ребра:');
for i:= 1 to m do
Begin
readln(f, b[i, 1], b[i, 2]); // Чтение списка ребер из файла
writeln(i, ') ', b[i, 1], ' - ', b[i, 2]);
if b[i, 1] = b[i, 2] then
c:= c + 1;
t:= t - [b[i, 1], b[i, 2]];
end;
k:= 0;
foreach var r in t do
k:= k + 1;
writeln;
close(f);
while m > 0 do
Begin
t:= [];
t:= t + [b[1, 1], b[1, 2]];
b[1, 1]:= b[m, 1];
b[1, 2]:= b[m, 2];
m:= m - 1;
yes:= true;
while (m > 0) and yes do
Begin
yes:= false;
for i:= 1 to m do
if (b[i, 1] in t) or (b[i, 2] in t) then
Begin
t:= t + [b[i, 1], b[i, 2]];
b[i, 1]:= b[m, 1];
b[i, 2]:= b[m, 2];
m:= m - 1;
yes:= true;
end;
end;
k:= k + 1;
end;
writeln('Количество петель = ', c);
//writeln('Количество изолированных вершин = ',k);
writeln('Количество компонентов связности = ', k);
end.
РЕЗУЛЬТАТЫИСПЫТАНИЙ
Приложение Б
(обязательное)
Рисунок Б.1