Размещено на http://www.allbest.ru/

Курсовая работа

«Структуры данных и алгоритмы»

Введение

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

абстрактных структур данных (списки, стеки, очереди, деревья, графы, таблицы),

алгоритмов поиска (линейный поиск, бинарный поиск, исчерпывающий поиск),

алгоритмов обхода иерархических структур в ширину, в глубину,

алгоритмов, оперирующих со структурами типа граф,

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

Задания на курсовую работу разбиты по темам: графы, системы дорог, деревья, языки, грамматики, логические формулы, выражения, игры.

Требования к выполнению курсовой работы

1. Решая задачу необходимо:

- сделать формальную (на языке математики) постановку задачи

- продумать и обосновать метод решения задачи;

- продумать и обосновать формы представления (внешнего и внутреннего) исходных данных и результатов задачи, т.е. спецификации данных;

- реализуя решение, использовать принципы структурного и модульного программирования.

2. Отчет по КР включает следующие разделы:

1. Условие задачи

2. Анализ задачи

3. Структуры данных, используемые для представления исходных данных и результатов задачи

4. Укрупненный алгоритм решения задачи

5. Структура программы

6. Текст программы на языке С

7. Набор тестов (в форме, соответствующей предметной области задачи)

8. Результаты работы программы

Анализ задачи

Данный пункт включает:

- определение исходных данных и результатов решения задачи;

- установление основных отношений (в виде математических формул, зависимостей и т.п.) между входными и выходными данными задачи;

- выделение основных подзадач, которые надо решить, чтобы достичь результата;

- выбор и описание метода ее решения. Метод решения должен быть описан на языке математики и предметной области задачи.

Структуры данных

В данном пункте определяются и описываются формы представления (внешнего и внутреннего) исходных данных и результатов задачи.

Алгоритм решения задачи

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

Структура программы

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

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

Набор тестов

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

Оформление отчета

1. Отчет оформляется на стандартных листах бумаги формата А4 (297210 мм) или листах школьной тетради, желательно в напечатанном виде. Записи ведутся только на одной стороне листа.

1. Некоторые основные определения

Математические модели большого числа задач могут быть описаны в терминах теории графов, поэтому алгоритмы исследования структуры (обработки) графов, а также способы их представления очень важны. Графом (неориентированным графом) G(V,E) называется совокупность двух множеств, где V - конечное непустое множество элементов, называемых вершинами, а E - множество неупорядоченных пар различных элементов множества V (эти пары называются ребрами). Граф, состоящий из одной вершины, называется тривиальным.

Говорят, что ребро e = (u, v) соединяет вершины u и v. Ребро e и вершина u (а также e и v) называются инцидентными, а вершины u и v смежными. Ребра инцидентные одной и той же вершине также называются смежными.

Степень вершины - это число ребер, инцидентных ей. Вершина графа, имеющая степень 0, называется изолированной, а имеющая степень 1 - висячей.

Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

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

Граф называется простым, если любая пара вершин соединена не более чем одним ребром и граф не имеет петель.

Маршрут (путь) - это чередующаяся последовательность

a = v₀ , e₁ , v₁ , , e₂ , . . . , v_n-1, e_n , v_n = b

вершин и ребер графа такая, что e_i = (v_i-1 , v_i), 1 ? i ? n. Говорят, что маршрут соединяет вершины a и b - концы маршрута. В простом графе маршрут можно задать перечислением лишь его вершин a = v₀ , v₁ , . . . , v_n = b или его ребер e₁ , e₂, e_n.

Маршрут называется цепью, если все его ребра различные. Маршрут называется замкнутым, если v₀ = v_n.

Замкнутая цепь называется циклом. Цепь называется простой, если не содержит одинаковых вершин. Простая замкнутая цепь называется простым циклом.

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа.

Вершина u достижима из вершины v, если существует путь из v в u.

Длина пути v₀ , v₁ , . . . , v_n равна числу его ребер, т.е. n.

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины.

Часть графа G(V,E) - это такой граф G'(V',E'), что V' V и E' E.

Подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u, v содержит и ребро (u, v), если оно есть в G.

Дополнением графа G называется граф G' с тем же множеством вершин, что и у G, причем две различные вершины смежны в G' тогда и только тогда, когда они несмежны в G. Ребра графов G и G' вместе образуют полный граф. Граф называется полным, если любые две его вершины смежны.

Два графа G1 и G2 изоморфны, если существует взаимно однозначное отображение множества вершин графа G1 на множество вершин графа G2, сохраняющее смежность.

Граф называется связным, если для любой пары вершин существует соединяющий их путь. Максимальный связный подграф несвязанного графа называется компонентой связности данного графа.

Если задана функция F: V>M, то множество M называется множеством пометок, а граф называется помеченным. Если задана функция F: E>M, т.е. ребрам графа приписаны веса, то граф называется взвешенным.

Ребро графа называется ориентированным, если существенен порядок расположения его концов. Граф, все ребра которого ориентированные, называется ориентированным графом (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества E - дугами. Дуга (u, v) ведет от вершины u к вершине v, Вершину v называют преемником вершины u, а u - предшественником вершины v. Понятия части орграфа, пути, расстояния, простого и замкнутого пути, цикла определяются для орграфа так же, как и для графа, но с учетом ориентации дуг.

Источник орграфа - это вершина, от которой достижимы все остальные вершины. Сток орграфа - это вершина, достижимая со всех других вершин.

Деревом называется связный граф без циклов.

Корневое дерево - это связный орграф без циклов, удовлетворяющий условиям:

имеется единственная вершина, называемая корнем, в которую не входит ни одна дуга;

к каждой некорневой вершине ведет ровно одна дуга.

Вершины, из которых не выходит ни одна дуга, называются листьями.

2. Представление графов в ЭВМ

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

2.1 Матрица смежности

Матрицей смежности помеченного графа с n вершинами называется матрица

A=[ a_ij], i, j = 1,2, n,

в которой

Матрица смежности однозначно определяет граф (см. рис. 1.). Для неориентированного графа матрица A является симметричной относительно главной диагонали. Число единиц в строке равно степени соответствующей вершины. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.

Преимуществом такого представления является “прямой доступ” к ребрам графа, т.е. имеется возможность за один шаг получить ответ на вопрос “существует ли в графе ребро (x, y)?”. Для небольших графов, когда места в памяти достаточно с матрицей смежности часто проще работать. Недостаток заключается в том, что независимо от числа ребер объем занимаемой памяти составляет n n или n n/2- n, если использовать симметрию и хранить только треугольную подматрицу матрицы смежности. Кроме того, каждый элемент матрицы достаточно представить одним двоичным разрядом.

2.2 Матрица инцидентности

Матрицей инцидентности называется матрица B = [b_ij ], i =1, 2, . . . , n, j = 1,2, . . . , m (где n - число вершин, а m - число ребер графа), строки которой соответствуют вершинам, а столбцы - ребрам. Элемент матрицы в неориентированном графе равен:

В случае ориентированного графа с n вершинами и m дугами элемент матрицы инцидентности равен:

Строки матрицы также соответствуют вершинам, а столбцы - дугам.

Матрица инцидентности однозначно определяет структуру графа (см. рис. 1.1. а-в, д-ж). В каждом столбце матрицы B ровно две единицы. Равных столбцов нет.

Недостаток данного представления состоит в том, что требуется n m единиц памяти, большинство из которых будет занято нулями. Не всегда удобен доступ к информации. Например, для ответа на вопросы “есть ли в графе дуга (x, y)?” или “к каким вершинам ведут ребра из вершины x?” может потребоваться перебор всех столбцов матрицы.

2.3 Матрица весов

Простой взвешенный граф может быть представлен своей матрицей весов W =[w_ij], где w_ij - вес ребра, соединяющего вершины i, j = 1,2, ... , m. Веса несуществующих ребер полагаются равными ? или 0 в зависимости от задачи. Матрица весов является простым обобщением матрицы смежности.

2.4 Список ребер графа

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

x = (x₀ , x₁ , . . . , x_m )

y = (y₀ , y₁ , . . . , y_m ),

где m -- количество ребер в графе. Каждый элемент в массиве есть метка вершины, а i-е ребро графа выходит из вершины x_i и входит в вершину y_i. Объем занимаемой памяти составляет в этом случае 2m единиц памяти. Неудобством является

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

2.5 Списки смежных вершин графа

Граф может быть однозначно представлен структурой смежности своих вершин. Структура смежности состоит из списков Adj [x] вершин графа, смежных с вершиной x. Списки Adj [x] составляются для каждой вершины графа. Структура смежности может быть удобно реализована массивом из n (число вершин в графе) линейно связанных списков (см. 1.1. а-г). Каждый список содержит вершины, смежные с вершиной, для которой составляется список. Список смежных вершин графа дает компактное представление для разреженных графов - тех, у которых множество ребер много меньше множества вершин. Недостаток этого представления таков: если мы хотим узнать, есть ли в графе ребро (x, y), приходится просматривать весь список Adj [x] в поисках y. Объем требуемой памяти составляет для ориентированных

Размещено на http://www.allbest.ru/

Рис. 1.

n+ m и n+2m для неориентированных графов единиц памяти, где n - число вершин графа, а m - число ребер (дуг) графа. Если в основе алгоритма решения задачи лежат операции добавления и удаления вершин из списков, то хранение списков смежности удобно реализовать, используя связанное представление списков (см. 1.).

3. Обход графа

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

3.1 Обход (или поиск) в глубину

Пусть задан граф и фиксирована начальная вершина s (исходный граф может быть неориентированным или ориентированным). Стратегия поиска в глубину состоит в том, чтобы, начиная с начальной вершины, идти “вглубь”, пока это возможно (есть не пройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной. Если после этого остаются необнаруженные вершины, можно выбрать одну из них (как начальную вершину) и повторять процесс. Так делать до тех пор, пока мы не обнаружим все вершины графа.

Когда при поиске мы впервые обнаружим вершину v, смежную с вершиной u, необходимо отметить это событие. Алгоритм поиска в глубину использует для этого цвета (метки) вершин. Каждая из вершин вначале белая (не пройденная). Будучи обнаруженной, она становится серой. Когда вершина будет полностью обработана (т.е. когда список смежных с ней вершин будет просмотрен), она станет черной. Таким образом, в процессе поиска из графа выделяется часть - “дерево поиска в глубину” или несколько деревьев (лес поиска в глубину), если поиск повторяется из нескольких вершин. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Кроме этого можно ставить дополнительные метки на вершинах дерева: метку, когда вершина была обнаружена (сделалась серой) и метку, когда была закончена обработка списка смежных с u вершин (и u стала черной).

Приведенный ниже алгоритм использует представление графа списками смежных вершин Adj [u]. Для каждой вершины u графа дополнительно хранятся ее цвет Mark[u] и ее предшественник Pr[u]. Если предшественника нет (например, если u = s или u еще не обнаружена), то Pr[u ] = nil. Кроме того, в d [u] и f [u] записываются дополнительные для u метки: метки времени. В d [u] записывается время, когда вершина u была обнаружена (и стала серой), а в f [u] записывается время, когда была закончена обработка списка смежных с u вершин (и u стала черной). В приводимом ниже алгоритме метки времени d [u] и f [u] это целые числа от 1 до 2¦V¦; для любой вершины u выполнено неравенство: d [u] < f [u]. Вершина u будет белой до момента d [u], серой между d [u] и f [u] и черной после f [u]. Алгоритм использует рекурсию для просмотра всех смежных с u вершин.

Поиск в глубину (G)

1 {

2 for ( каждая вершина u V[G] )

3 { Mark [u]<БЕЛЫЙ;

4 Pr [u] <nil;

5 }

6 time <0;

7 for ( каждая вершина s V[G] )

8 if (Mark [s] = БЕЛЫЙ) Search (s);

9 }

Search (u)

1 {

2 Mark [u] <СЕРЫЙ;

3 d [u] <time<time+1;

4 for (каждая v Adj [u])

5 { if (Mark [v] = БЕЛЫЙ)

6 { Pr [v] <u; Search (v); }

7 }

8 Mark [u] <ЧЕРНЫЙ;

9 f [u] < time<time+1;

10 }

Алгоритм начинается с того, что сначала (строки 2-5) все вершины красятся в белый цвет (помечаются как не пройденные); в поле Pr помещается nil (пока у вершин нет предшественника). Затем (строка 6) устанавливается начальное (нулевое) время (переменная time - глобальная переменная). Для всех вершин (строки 7-8), которые все еще остались не пройденными (белыми), вызывается процедура Search. Эти вершины становятся корнями деревьев поиска в глубину.

В момент вызова Search (u) вершина u - белая. В процедуре Search она сразу же становится серой (строка 2). Время ее обнаружения (строка 3) заносится в d[u] (счетчик времени перед этим увеличился на единицу). Затем просматриваются (строки 4-7) смежные с u вершины; процедура Search вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с u вершин саму вершину u делаем черной и записываем в f [u] время этого события.

3.2 Примеры решения задач методом поиска в глубину

Рассмотрим использование метода поиска в глубину на двух простых примерах.

Задача 1. Для неориентированного графа G(V,E) требуется найти ребра дерева поиска в глубину (древесные и обратные).

Для решения этой задачи достаточно пройти граф в глубину и сохранить информацию о пройденных ребрах дерева поиска в глубину и об обратных ребрах, если такие есть. Если граф не связен, то будем находить ребра всех деревьев поиска. Алгоритм решения этой задачи полностью соответствует общей схеме прохода в глубину. В качестве “серых” меток обнаруженных вершин будем использовать целые числа в диапазоне от 0 до ¦V¦-1, это позволит просто различать обратные ребра. Считаем, что вершины графа помечены целыми числами от 0 до ¦V¦-1. Граф задан структурой смежности Adj [u]. Ребра дерева поиска (и обратные ребра) запоминаются в массиве T, а в массиве B запоминается признак ребра: 1 - ребро дерева, 0 - обратное ребро.

Программа нахождения ребер дерева поиска в глубину (язык Си)

# include <stdio.h>

# define maxn 100 //максимальное число вершин в графе

# define maxADj 1000 // максимальная длина списка смежности графа

int nT, count;

int Adj [maxADj]; //список смежности графа

int Fst [maxn]; //указатели на списки смежности для каждой v V

int Nbr [maxn]; //число вершин в списке смежности для каждой v V

int Vt [maxn]; //список вершин графа

int Mark [maxn]; //метки вершин графа

int T [maxn]; //последовательность ребер при проходе в глубину

int B [maxn]; //признаки основных и обратных ребер при проходе

//графа в глубину

//функция прохода графа в глубину и нахождения ребер дерева поиска

void Depth ( int x, int s)

{

int i, v;

count ++;

Mark [x] = count; // вершина x помечается как пройденная вершина

for (i = 0; i < Nbr[x]; i++) //просмотр списка смежности вершины x

{ v = Adj [Fst [x] + i]; //выбор из списка смежности x еще не

if (Mark [v] = = -1) //пройденной вершины

{ nT = nT +2; T [nT - 1] = x; T [nT] = v;

B [nT/2] = 1; //установлен признак основного ребра

Depth (v, x);

}

else

if ( Mark [v] < Mark [x] && v != s )

{ nT = nT +2; T [nT - 1] = x; T [nT] = v;

B [nT/2] = 0; //установлен признак обратного ребра

}

}

}

//функция обнаружения не пройденных вершин графа

void WayDepth (void)

{

int u;

nT = -1; //глобальная переменная для вычисления индекса

//в массивах T и B

count = -1; //глобальная переменная для вычисления меток

//обнаруженных вершин

for (u = 0; u < n; u++) Mark[u] = -1; //сначала все вершины графа

//помечаем как не пройденные

for (u = 0; u < n; u++) //выбор очередной не пройденной

if (Mark[u] = = -1) Depth (u, -1); // вершины

}

void main ( void )

{

File *p, *f;

int i, j, n;

// ввод исходных данных

p = fopen( “spisok_Adj.in”, “r” );

if (fscanf (p, “%d”, &n ) != EOF)

{Fst [0] = 0; //установка указателя начала списка смежности для

//первой вершины

for ( i = 0; i < n; i++)

{ fscanf (p, “%d”, &Vt [i] ); //ввод метки вершины

fscanf (p, “%d”, &Nbr [i] ); //ввод числа вершин в списке

// смежности вершины i

for ( j = 0; j < Nbr [i]; j++ ) //ввод списка смежности вершины i

fscanf (p, “%d”, &Adj [ Fst [i] + j] );

Fst [i + 1] = Fst [i] + Nbr [i]; //установка указателя начала

//списка смежности следующей вершины

}

WayDepth ( ); // Проход графа в глубину

// вывод результатов

f = fopen( “spisok_reber.out”, “w” );

for ( i = 0; i < nT/2; i++ )

printf (f, “%d “, Vt [ T[2*i - 1] ] );

printf (f, “\n”);

for ( i = 0; i < nT/2; i++ )

printf (f, “%d “, Vt [ T[2*i ] ] );

printf (f, “\n”);

for ( i = 0; i < nT/2; i++ )

printf (f, “%d “, B [ i ] );

printf (f, “\n”);

fclose ( p ); fclose ( f );

}

Структура смежности графа:

v Adj [v]

0 1, 2, 4

1 0, 2, 3

2 0, 1, 3, 4

3 1, 2

4 0, 2, 5, 6

5 4, 6

6 4, 5

Рис.2.

Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в следующем формате:

* в первой строке файла содержится число вершин графа;

* далее для каждой вершины в отдельной строке указывается номер самой вершины, число вершин смежных с данной, и список этих вершин (вершины перечисляются в порядке возрастания меток вершин).

Исходный файл для графа на рис. 2:

7

0 3 1 2 4

1 3 0 2 3

2 4 0 1 3 4

3 1 1 2

4 4 0 2 5 6

5 2 4 6

6 2 4 5

В программе эта структура реализована в массивах Vt, ADj, Fst, Nbr, имеющих следующий вид:

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Vt [x]	0	1	2	3	4	5	6
Adj [x]	1	2	4	0	2	3	0	1	3	4	1	2	0	2	5	6	4	6	4	5
Nbr [x]	3	3	4	2	4	2	2
Fst [x]	0	3	6	10	12	16	18

Данное отображение структуры смежности позволяет обращаться к элементам массивов по номерам (меткам) соответствующих вершин.

Операция v ADj [x] в программной реализации представляется как for (i = 0; i < Nbr[x]; i++) v = Adj [Fst [x] + i], где Nbr[x] - количество вершин в структуре смежности для вершины x; Adj [x] - массив, содержащий списки смежности для каждой вершины; Fst [x] - номер первой вершины в списке смежности, соответствующем вершине x, тогда Fst [x] + i - номер i - й вершины в списке смежности, соответствующем вершине x. Например, пусть x = 3, тогда Fst [3] = 10 и Nbr [3] = 2 (в списке смежности вершины x два элемента), элементы Adj [ Fst [3] + 0] = Adj [10] = 1 и Adj [Fst [3] + 1] = Adj [11] = 2 составляют список смежности вершины x = 3.

Решение задачи начинается с вызова функции WayDepth, которая сначала помечает в массиве Mark все вершины как не пройденные (красит их меткой равной -1). Затем из вершин выбирается очередная (в порядке возрастания меток вершин) не пройденная вершина. Эта вершина рассматривается как корень дерева поиска в глубину и для нее запускается функция Depth, реализующая проход графа в глубину. Функция Depth помечает в массиве Mark эту вершину как обнаруженную (красит ее значением целой переменной count, т.е. пройденные вершины постепенно нумеруются от 0 до ¦V¦ по мере того, как в них попадаем). Затем просматривается список смежности вершины, для которой запущена функция Depth. Если в этом списке есть еще не пройденные вершины (т. е. метка Mark [v] вершины v равна -1), то ребро (x, v) добавляется к множеству основных ребер дерева поиска в глубину (вершины x и v помещаются в массив T). Процесс прохода графа в глубину в этом случае продолжается, начиная с не пройденной вершины v (для вершины v запускается функция Depth). Когда в списке смежности вершины x обнаружена пройденная вершина, то при Mark [v] ? -1 ребро (x, v) будет являться обратным ребром, если Mark [v] < Mark [x] и v ? s. Условие Mark [v] < Mark [x] означает, что вершина v была пройдена раньше вершины x. Поэтому ребро (x, v) будет обратным, если оно не является ребром дерева поиска, пройденным от предка s к x, т. е. v ? s.

Решение заканчивается, когда будут просмотрены все вершины графа (т. е. все элементы массива Mark станут отличны от -1).

Дерево поиска в глубину для графа на рис. 2. имеет следующий вид:

Сплошными линиями отмечены ребра дерева, которые были пройдены во время обхода графа в глубину, пунктирными - обратные ребра.

Состояния рабочих массивов Mark, T и B после завершения алгоритма приведены ниже:

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
Mark [x]	0	1	2	3	4	5	6
T [x]	0	1	1	2	2	0	2	3	3	1	2	4	4	0	4	5	5	6	6	4
B [x]	1	1	0	1	0	1	0	1	1	0

Результаты работы выводятся в файл spisok_reber.out в следующем формате:

* в первой строке файла метки начальных вершин ребер дерева поиска в глубину;

* во второй строке файла метки конечных вершин ребер дерева поиска в глубину;

* в третьей строке файла признаки ребер: значение 1 - признак основного ребра, значение 0 - признак обратного ребра.

Выходной файл для графа на рис. 2.:

1 2 2 3 2 4 4 5 6

2 0 3 1 4 0 5 6 4

1 0 1 0 1 0 1 1 0

Задача 2. В неориентированном графе G(V,E) требуется выделить компоненты связности.

Так как граф неориентированный, то для нахождения компонент связности достаточно пройти граф в глубину, пока остаются не пройденные вершины, при этом помечая вершины одной компоненты связности одинаковыми метками. Для этого достаточно использовать переменную, значение которой изменяется, если полностью пройдена компонента связности (в данной программе это глобальная переменная count). Компонента связности при проходе в глубину будет полностью пройдена, когда в списках смежности вершин этой компоненты не станется не пройденных вершин. Вершины графа помечены целыми числами. Граф задан структурой смежности Adj [u].

Программа выделения компонент связности - поиск в глубину (язык Си)

# include <stdio.h>

# define maxn 100 //максимальное число вершин в графе

# define maxADj 1000 // максимальная длина списка смежности графа

int n, count = 0;

int Adj [maxADj]; //список смежности графа

int Fst [maxn]; //указатели на списки смежности для каждой v V

int Nbr [maxn]; //число вершин в списке смежности для каждой v V

int Vt [maxn]; //список вершин графа

int Mark [maxn]; //метки вершин графа

//функция прохождения одной компоненты связности

void Component ( int u )

{

int i, v;

Mark [u] = count; // вершина u помечается как пройденная вершина

for (i = 0; i < Nbr [u ]; i++) //просмотр списка смежности вершины u

{ v = Adj [Fst [u ] + i]; //выбор из списка смежности u еще не

if (Mark [v] = = 0) //пройденной вершины

Component (v );

}

}

//функция поиска не пройденных вершин графа, т.е. новой компоненты связности

void STRONGL_Comp2 (void)

{

int u;

for (u = 0; u < n; u++) Mark[u] = 0; //сначала все вершины графа

//помечаем как не пройденные

for (u = 0; u < n; u++) //выбор очередной не пройденной вершины

if (Mark[u] = = 0)

{ count ++; //увеличение числа компонент связности

Component (u );

}

void main ( void )

{

File *p, *f;

int i, j, n;

// ввод исходных данных

p = fopen( “spisok_Adj.in”, “r” );

if (fscanf (p, “%d”, &n ) != EOF) //ввод числа вершин графа

{Fst [0] = 0; //установка указателя начала списка смежности для

//первой вершины

for ( i = 0; i < n; i++)

{ fscanf (p, “%d”, &Vt [i] ); //ввод метки вершины

fscanf (p, “%d”, &Nbr [i] ); //ввод числа вершин в списке

// смежности вершины i

for ( j = 0; j < Nbr [i]; j++ ) //ввод списка смежности вершины i

fscanf (p, “%d”, &Adj [ Fst [i] + j] );

Fst [i + 1] = Fst [i] + Nbr [i]; //установка указателя начала

//списка смежности следующей вершины

}

STRONGL_Comp2 ( ); // Проход графа в глубину, поиск компонент связности

// вывод результатов

f = fopen( “component.out”, “w” );

for ( i = 0; i < n; i++ )

printf (f, “%d “, Vt [ i ] );

printf (f, “\n”);

for ( i = 0; i < n; i++ )

printf (f, “%d “, Mark [ i ] );

fclose ( p ); fclose ( f );

}

Рассмотрим работу программы на примере неориентированного графа, представленного на рис. 3. В графе 11 вершин, вершины помечены целыми числами, начиная с 1.

Рис.3.

Структура смежности этого графа:

v Adj [v]

1 2, 3, 4

2 1, 3

3 1, 2, 4

4 1, 3

7 8, 9

8 7

9 7

12 14, 15, 21

14 12, 15

15 12, 14

21 12

Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в формате аналогичном задаче 1.

Исходный файл для графа на рис. 3:

11

1 3 2 3 4

2 2 1 3

3 3 1 2 4

4 2 1 3

7 2 8 9

8 1 7

9 1 7

12 3 14 15 21

14 2 12 15

15 2 12 14

21 1 12

В программе эта структура реализована в массивах Vt, ADj, Fst, Nbr, метки компонент - в массиве Mark. Состояния массивов после выполнения программы приведены ниже.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
Vt [u]	1	2	3	4	7	8	9	12	14	15	21
Nbr [u]	3	2	3	2	2	1	1	3	2	2	1
Fst [u]	0	3	5	8	10	12	13	14	17	19	21
Adj [u]	2	3	4	1	3	1	2	4	1	3	8	9	7	7	14	15	21	12	15	12	14	12
Mark [x]	1	1	1	1	2	2	2	3	3	3	3

Результаты работы выводятся в файл component.out в следующем формате:

* в первой строке файла метки вершин графа;

* во второй строке файла номера компонент связности.

Выходной файл для графа на рис. 3:

1 2 3 4 7 8 9 12 14 15 21

1 1 1 1 2 2 2 3 3 3 3

3.3 Обход (или поиск) в ширину

Пусть задан граф (исходный граф может быть неориентированным или ориентированным) и фиксирована начальная вершина s. В процессе поиска мы идем вширь, а не вглубь: сначала просматриваем все соседние с s вершины, затем соседей и т. д. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по ребрам) вершины в порядке возрастания расстояния от s. Расстоянием считается длина (число ребер) кратчайшего пути. В процессе поиска из графа выделяется часть, называемая “деревом поиска в ширину” с корнем s. Оно содержит все достижимые из s вершины (и только их). Для каждой из этих вершин путь из корня (вершины s) в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Алгоритм также использует цвета вершин. Вначале все вершины белые (не пройденные), в процессе поиска белая вершина может стать серой, если она обнаружена, а серая - черной. Различие между серой и черной вершиной позволяет поддерживать такое свойство: если (u,v) E и u черная, то v - серая или черная вершина. Таким образом, только серые вершины могут иметь смежные необнаруженные вершины.

Вначале дерево поиска в ширину состоит только из корня - начальной вершины s. Как только обнаружена белая вершина v, смежная с ранее найденной вершиной u, вершина v (вместе с ребром (u,v)) добавляется к дереву поиска, становясь потомком вершины u, а u становится родителем v. Каждая вершина обнаруживается только однажды, так что двух родителей у нее быть не может.

Приведенный ниже алгоритм использует представление графа списками смежных вершин Adj [u]. Для каждой вершины u графа дополнительно хранятся ее цвет Mark [u] и ее предшественник Pr [u]. Если предшественника нет (например, если u = s или u еще не обнаружена), то Pr [u ] = nil. Кроме того, в d [u] записывается расстояние от s до u. Алгоритм также использует очередь Q для хранения множества серых вершин.

Поиск в ширину (G, s)

1 {

2 for (каждая вершина u V[G] -{s})

3 { Mark [u]<БЕЛЫЙ;

4 d [u] <?;

5 Pr [u] <nil; }

6 Mark [s] <СЕРЫЙ;

7 d [s] <0;

8 Pr [s] <nil;

9 Q<{s};

10 While (Q ? )

11 { u<head [Q];

12 for (каждая вершина v Adj [u])

13 { if (Mark [v] = БЕЛЫЙ)

14 { Mark [v]<СЕРЫЙ; d [v]<d [u]+1;

15 Pr [v]<u; InQUEUE (Q, v); }

16 }

17 OutQUEUE (Q);

18 Mark [u] <ЧЕРНЫЙ;

19 }

20 }

Сначала все вершины, кроме начальной s становятся белыми, все значения d бесконечными, а предком всех вершин объявляется nil (строки 1- 4 алгоритма). Затем начальная вершина считается обнаруженной и красится в серый цвет, расстояние d [s] объявляется равным 0, а предшественником вершины s объявляется nil (строки 5-7). Вершина s помещается в очередь Q (строка 8), и начинается проход графа в ширину. Основная часть алгоритма выполняется пока очередь не пуста, то есть существуют серые вершины (вершины, которые уже обнаружены, но списки смежности которых еще не просмотрены). Вершина, находящаяся в начале (голове) очереди помещается в u (строка 10). Для вершины u просматриваются все смежные с ней вершины (строки 11-16). Обнаружив среди них белую вершину, делаем ее серой (строка 13), объявляем u ее родителем (строка 15) и устанавливаем расстояние до вершины v равным d [u] + 1 (cтрока 14). Затем эта вершина добавляется в конец очереди Q (строка 16). Когда список смежности вершины u просмотрен полностью, удаляем вершину u из очереди, перекрасив ее в черный цвет (строки 17-18).

3.4 Пример решения задачи методом поиска в ширину

Задача 3. В неориентированном графе G(V,E) найти все вершины недостижимые от заданной вершины.

В неориентированном графе вершины недостижимые от заданной - это вершины, принадлежащие другой компоненте связности, чем заданная вершина. Поэтому, чтобы решить эту задачу достаточно пройти граф в глубину или в ширину, начиная с заданной вершины и пометить все вершины, которые встречаются при обходе. Когда будут пройдены все вершины компоненты связности, которой принадлежит заданная вершина, все вершины, оставшиеся не пройденными, являются недостижимыми. Поскольку в процессе обхода достаточно просто пометить вершину как пройденную, то лучшим решением будет нерекурсивная реализация обхода графа. В данной задаче воспользуемся возможностью различать при обходе вершины обнаруженные (серые вершины) и уже обработанные (черные). В этом случае при обходе в ширину достаточно использовать массив меток Mark со следующими значениями: 0 - не обнаруженная вершина, 1 - обнаруженная, 2 - обработанная вершина. Вершины графа помечены числами от 1 до ¦V¦. Граф задан структурой смежности.

Программа поиска недостижимых вершин ( поиск в ширину) (язык Си)

# include <stdio.h>

# include <alloc.h>

# define SI sizeof (int)

struct VER //элемент структуры смежности графа

{ int kol;

int mv;

int *adj; };

int n; //глобальная переменная - число вершин

struct VER *Vt; //указатель на массив структур смежности

File *p, *f;

//функция ввода списков смежности графа

void vvod_graf ( )

{

int i, j, N, kol;

p = fopen( “spisok_Adj.in”, “r” );

if (fscanf (p, “%d”, &n ) != EOF) //ввод числа вершин графа

{Vt = (struct VER *) calloc (n, SI); //выделение памяти основным элементам

//структуры смежности графа

for ( i = 0; i < n; i++)

{ fscanf (p, “%d”, &Vt [i] . mv ); //ввод метки вершины графа

fscanf (p, “%d”, &Vt [i] . kol ); //ввод числа вершин в списке смежности

kol = Vt [i].kol; //вершины i

Vt [i] . adj = (int*) calloc (kol, SI); //выделение памяти списку смежности

if (kol)

for ( j = 0; j < kol; j++ ) //ввод списка смежности i-й вершины

{ fscanf (p, “%d”, &N ); Vt [i]. adj [j] = N - 1; }

}

}

fclose ( p );

}

//функция прохождения графа с заданной вершины

void proverka ( int u )

{

int i, v, flag = 1;

Mark [u] = 2; // вершина u помечается как обработанная вершина

while (flag) //прохождение графа, пока есть необнаруженные

{ //вершины компоненты связности вершины u

for (i = 0; i < Vt [u ] . kol; i++) //просмотр списка смежности вершины u

{ v = Vt [u ] . adj[i]; //выбор из списка смежности u вершины

if (Mark [v] = = 1) //если вершина v уже была обнаружена,

Mark [v] = 2; //то считать ее обработанной

else if (! Mark [v] ) Mark [v] = 1; //если вершина v обнаружена сейчас,

} //то считать ее обнаруженной

for (i = 0; i < n && Mark [i] != 1; i++) ; //просмотр списка меток и поиск вершин

if (i ==n) flag = 0; //обнаруженных на предыдущем шаге

else { u = i; Mark [u] = 2; } //если такая вершина есть, то продолжаем

} //обход, начиная с этой вершины

}

void main ( void )

{

int i, s, flag;

// ввод исходных данных

vvod_graf ( );

Mark = (int*) calloc ( n, SI ); //выделение памяти под массив меток

for ( i = 0; i < n; i++) Mark [i] = 0;

printf (“\n Задайте исходную вершину”);

scanf ( “%d”, &s ); //ввод метки исходной вершины

s --;

proverka ( s ); //проход графа, начиная с заданной вершины

// вывод результатов

f = fopen( “spisok.out”, “w” );

printf (f, “%d “, s +1 );

printf (f, “\n“ );

for ( i = 0; i < n; i++ )

if (i != s && ! Mark [i] ) //все необнаруженные после прохода графа вершины

printf (f, “%d “, Vt [ i ] . mv); //выводятся как не достижимые из заданной s

printf (f, “\n”);

fclose ( f );

}

Рассмотрим работу программы на примере неориентированного графа, представленного на рис. 4. В графе 9 вершин, вершины помечены целыми числами, начиная с 1.

Рис. 4.

Исходные данные структуры смежности графа задаются в текстовом файле spisok_Adj.in в формате аналогичном задаче 1.

Исходный файл для графа на рис. 4.:

9

1 3 2 3 4

2 2 1 3

3 3 1 2 4

4 2 1 3

5 1 6

6 1 5

7 2 8 9

8 1 7

9 1 7

В программе эта структура реализована в массиве динамической памяти Vt, элементы которого представлены структурой, содержащей номер вершины, число смежных с ней вершин, указатель на список смежности. Списки смежности также хранятся в массивах динамической памяти. Метки вершин одной компоненты связности - в массиве Mark. Значения элементов структуры смежности заданного графа приведены на рис. 5.

Размещено на http://www.allbest.ru/

Рис. 5.

Пусть задана вершина (для которой находим все недостижимые от нее вершины) s = 2. Вначале все вершины помечаются нулем (в массиве Mark) как не обнаруженные (белые). Заданную вершину сразу помечаем как обработанную (меткой 2). И пока есть не обработанные вершины (flag = = 1) просматриваем списки смежности, начиная со списка смежности заданной вершины. Затем списки смежности вершин смежных с заданной и т. д. При этом помечая обнаруженные смежные с текущей вершиной вершины единицей. Текущая вершина перед просмотром ее списка смежности помечается как обработанная (меткой 2). Обход графа в ширину осуществляется в соответствии с порядком нумерации вершин графа и обеспечивается тем, что поиск еще не обработанных вершин начинается всегда с первой вершины. Проход графа в ширину заканчивается, когда среди меток вершин в массиве Mark не будет найдена метка со значением 1 (т.е. будут просмотрены все вершины одной компоненты связности). Вершины, метки которых остались равны 0 являются не достижимыми от заданной вершины. Состояния массива Mark после просмотра списка смежности очередной вершины отражены в таблице (для заданной вершины s = 2).

Mark	0	1	2	3	4	5	6	7	8
Начальное значение	0	0	0	0	0	0	0	0	0
После просмотра списка смежности вершины 2	1	2	1	0	0	0	0	0	0
После просмотра списка смежности вершины 1	2	2	2	1	0	0	0	0	0
После просмотра списка смежности вершины 3	2	2	2	2	0	0	0	0	0

Результаты работы программы выводятся в файл spisok.out в следующем формате:

* в первой строке файла метка (номер) заданной вершины графа;

* во второй строке файла метки (номера) не достижимых вершин графа, если все вершины достижимы вторая строка будет пустой.

Выходной файл для графа на рис.5:

2

5 6 7 8 9

4. Кратчайшие пути в графе

4.1 Кратчайшие пути в графе от одной вершины

Алгоритм поиска в ширину можно рассматривать как решение задачи о кратчайшем пути в частном случае, когда вес каждого ребра равен единице (т.е., граф не взвешенный). В полной задаче о кратчайшем пути нам дан ориентированный взвешенный граф G = (V, E) с весовой функцией w: E> R.

Весом пути p = (v₀ , v₁ , . . . , v_n ) называется сумма весов ребер, входящих в этот путь:

Вес кратчайшего пути из u в v равен

Кратчайший путь из u в v - это любой путь p из u в v, для которого w (p) = д (u, v). Если p = (v₁ , v₂ , . . . , v_k ) - кратчайший путь из v₁ в v_k и 1 ? i ? j ? k, то p_{i j} = (v_i , v_i+1 , . . . , v_j ) есть кратчайший путь из v_i в v_j .

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

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

На рис. 6. (а) приведен взвешенный ориентированный граф, в вершинах указаны веса кратчайших путей из вершины s. На следующих рисунках показаны (серыми ребрами) два его дерева кратчайших путей (б) и (в) с корнем s.

Размещено на http://www.allbest.ru/

Рис. 6.

Кратчайшие пути и релаксация

Релаксация является общим приемом в алгоритмах поиска кратчайших путей. Он состоит в постепенном уточнении верхней оценки на вес кратчайшего пути в данную вершину - пока неравенство не превратится в равенство. Для каждого ребра v V храним некоторое число d [v], являющееся верхней оценкой веса кратчайшего пути из начальной вершины s в вершину v (для краткости будем называть его просто оценкой кратчайшего пути). Начальное значение оценки кратчайшего пути для вершины s равно 0, для всех остальных вершин равно ? (d [s] = 0, d [v] = ? для остальных вершин). Релаксация ребра (u, v) E состоит в следующем: значение d [v] уменьшается до d [u] + w (u, v), если второе значение меньше первого; при этом d [v] остается верхней оценкой пути из s в v, так как для всякого ребра (u, v) E справедливо

д (s, v) ? д (s, u) + w(u, v).

4.2 Алгоритм Дейкстры

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G(V, E) с исходной вершиной s, в котором веса всех ребер неотрицательны (w (u, v) ? 0 для всех (u, v) E). электронный программа дейкстр

Алгоритм Дейкстры использует представление графа списком смежных вершин Adj [v]. В процессе работы алгоритма формируется множество S V, состоящее из вершин v, для которых д (s, v) уже найдено (то есть d [v] = д (s, v)). Роль множества S аналогична роли черных вершин при поиске в ширину. Осуществляя проход графа в ширину, начиная с начальной вершины s, алгоритм выбирает очередную вершину u V \ S с наименьшим d [u] , добавляет u к множеству S и производит релаксацию всех ребер, выходящих из u, после чего процесс повторяется. Вершины, для которых д (s, v) еще не найдено (т.е. не пройденные вершины), хранятся в очереди Q с приоритетами, определяемыми значениями оценок кратчайшего пути - d. Так как кроме весов кратчайших путей, как правило, требуется найти и сам путь, как и при поиске в ширину, для каждой вершины v V запоминается ее предшественник Pr [v] (предшественник вершины - это либо вершина, либо nil, если предшественника нет).

DIJKSTRA (G, w, s)

{ for ( каждая вершина v V)

{ d [v] < ?;

Pr [v]< nil; }

d [s] < 0;

S< 0;

Q < V [G];

while ( Q ? )

{ u< Extract-Min (Q);

S<S {u};

for ( каждая вершина v Adj [u] )

11 if ( d[v] > d [u] + w (u, v) )

12 {d [v]< d [u] + w (u, v); Pr [v]< u;}

13 }

14 }

Алгоритм начинается с инициализации (строки с 1- 4) оценок кратчайшего пути d и предшественников вершин Pr. Для всех вершин, кроме s оценки имеют бесконечные значения, для s оценка равна нулю. Предшественники вершин равны nil. Множество S инициализируется как пустое (строка 5). В очередь Q помещаются все вершины (строка 6). При каждом исполнении цикла (строки 7-13), пока очередь Q не пуста, из нее удаляется вершина u с наименьшим значением d [u] (строка 8 - вызов процедуры Extract-Min - удаление из очереди с приоритетом). Эта вершина добавляется к множеству S (строка 9) (первый раз это будет вершина u = s, так как при инициализации только d [s] имеет наименьшее значение, оно равно 0).

Затем просматриваются все вершины смежные с вершиной u (строки 10-12). Каждое ребро (u, v), выходящее из u, подвергается релаксации (строки 11-12). При этом для пути из s в вершину v могут измениться оценка кратчайшего пути d [v] и предшественник Pr [v], если d [v] > d [u] + w (u, v).

После завершения алгоритма для всех вершин u V будут выполняться равенства d [u] = д (s, u). По завершении поиска кратчайших путей цепочка предшественников в Pr, начинающаяся с произвольной вершины v, будет представлять собой кратчайший путь (точнее один из кратчайших путей) из s в v (в обратном порядке). Выполняя действия подобно процедуре Print_Path, приведенной выше, можно, используя Pr, легко найти эти пути.

Размещено на http://www.allbest.ru/

Рис. 7.

На рис. 7 для ориентированного взвешенного графа (а) последовательно показано выполнение алгоритма Дейкстры. Исходная вершина - s. В вершинах указаны оценки длин кратчайших путей. Серым цветом выделены ребра (f, g), для которых Pr [g] = f. Черные вершины - это вершины, которые лежат в множестве S, остальные находятся в очереди Q. Серая вершина имеет минимальное значение d и выбирается из очереди в качестве вершины u (что соответствует действию в строке 8 алгоритма). На рис. (б-е) показаны последовательные состояния после каждого выполнения цикла while. На рисунке (е) значения d и Pr - окончательные.