Выполнила Кулагина С.О.. ОПРЕДЕЛЕНИЯ Будем рассматривать задачу в терминах ориентированных графов. Граф – конечное множество V, называемое множеством. - презентация

1 Выполнила Кулагина С.О.

2 ОПРЕДЕЛЕНИЯ Будем рассматривать задачу в терминах ориентированных графов. Граф – конечное множество V, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение R и выделено множество E двухэлементных подмножеств V, определяемое как {a,b} E тогда и только тогда, когда (a,b) R и a b, и (b,a) не входит в Е. Вес – параметр дуги, длина дуги. Путь – сумма длин входящих в него дуг. Полустепенью исхода(захода) называется число исходящих (входящих) дуг. Две вершины – смежные, если они соединены дугой. Длина пути (во взвешенном графе) – весов дуг графа. Цикл – путь, который начинается и заканчивается в одной той же вершине и содержит как минимум 1 дугу. Ациклическим считается граф, не содержащий ни одного цикла. В разреженно м графе m

3 С ТРУКТУРА БИБЛИОТЕКИ STL Библиотека содержит пять основных видов компонентов: * алгоритм (algorithm): определяет вычислительную процедуру. * контейнер (container): управляет набором объектов в памяти. * итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера. * функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами. * адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

4 3 ВОЗМОЖНЫХ ПРЕДСТАВЛЕНИЯ Матрица смежности(vector >) – для насыщенного графа Структура смежности(vector > ) – Для разреженного графа Представление в форме map – Для представления при входе

5 И СПОЛЬЗУЕМЫЕ КЛАССЫ БИБЛИОТЕКИ. Для ввода- вывода Для представления графа в виде матрицы Для создания списков Для определения функторов Для создания очередей(на пример, для хранения вершин) Для создания векторов- структур, аналогичных массивам, но имеющих большую функциональ ность Для создания строк

6 П РЕДСТАВЛЕНИЕ ГРАФА : ВАРИАНТ 1 Если граф взвешенный: Представление графа в виде массива дуг с помощью STL map. Дуге(из 2-х вершин) сопоставляется её вес. Пример: представление визуальное и в форме map Пример: map >::iterator it; // Создание итератора для перехода по map Int i =10; it->first.push_back(i);// первая вершина Используем это представление для упорядочения графа на входе в программу

7 П РЕДСТАВЛЕНИЕ ГРАФА : ВАРИАНТ 2 Если граф насыщенный: Используется двумерная матрица смежности A. Для дуги (v i,w j ) с весом c i,j A[i][j] = c i,j Несуществующие дуги – значение «бесконечность» В STL представляется как vector >

8 П РЕДСТАВЛЕНИЕ ГРАФА : ВАРИАНТ 3 Если граф разреженный и связный: Используется структура смежности: массив списков. vector > Хранится вектор вершин, которым сопоставлены списки номеров вершин, смежных с ними. вершины Список смежных вершин Вес соответствующей дуги vector >::iterator it = new interator; Будем представлять граф именно так.

9 О БХОД В ШИРИНУ o Алгоритм: Выбираем непройденную вершину. Проверяем все рёбра и запоминаем непройденные вершины на их концах. Выбираем непройденную вершину и повторяем действия.

10 О БХОД В ШИРИНУ : КОД typedef pair vertex; typedef multimap ::iterator edgesIt; vector vertices; multimap edges; deque q; while(1) {current = q.front(); q.pop_front(); vector ::iterator vIt = find(vertices.begin(), vertices.end(), vertex(current.first, current.second)); (*vIt).second = true; cout

11 О БХОД В ГЛУБИНУ Алгоритм: Выбираем непройденную вершину Выбираем 1 из непройденных смежных вершин Если нет смежных непройденных вершин, то помечаем вершину пройденной и возвращаемся в запомненную вершину.

12 О БХОД В ГЛУБИНУ : КОД Рекурсивная реализация: vector > g; // граф int n; // число вершин vector used; void dfs (int v) { used[v] = true; for (vector ::iterator i=g[v].begin(); i!=g[v].end(); ++i) if (!used[*i]) dfs (*i); } Рекурсивный вызов

13 А ЛГОРИТМ Д ЕЙКСТРЫ В ориентированном графе с заданными длинами рёбер найти кратчайшие пути из одной вершины во все остальные. ЗАДАЧА

14 О ПРЕДЕЛЕНИЕ АЛГОРИТМА Алгоритм: Если – длина дуги (i,j). Шаг 0. Помечаем нулевую вершину индексом 0 Шаг i. Помечаем вершину i индексом λ i = min(λ i + λ ij ).

15 Н АЧАЛЬНЫЕ СТАДИИ АЛГОРИТМА Придаём всем вершинам бесконечные веса Отмечаем вершину - начало

16 Первый по очереди сосед вершины 1 вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7. Аналогичную операцию проделываем с двумя другими соседями 1-й вершины 3-й и 6-й.

17 Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и обсуждению не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена. Выберем следующую вершину

18 Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4. Первый (по порядку) сосед вершины 2 вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем. Следующий сосед вершины 2 вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = = 22. Поскольку 22

19 П ОВТОРЯЕМ АНАЛОГИЧНЫЕ ДЕЙСТВИЯ ДЛЯ ОСТАЛЬНЫХ ВЕРШИН

20 К ОД priority_queue, Cheapest> candidates; while(1){ for(list ::iterator p = outgoing_services[from].begin(); p!=outgoing_services[from].end();p++){ int b = cities[from]->total_distance+(*p)->distance; int c = cities[from]->from_city; if(cities[from]->visited==false){ if(cities[(*p)->destination]->total_fee==0) { cities[(*p)->destination]->total_fee = a; cities[(*p)->destination]->total_distance = b; cities[(*p)->destination]->from_city = c;} else if(cities[(*p)->destination]->total_fee>a) { cities[(*p)->destination]->total_fee=a; cities[(*p)->destination]->total_distance = b; cities[(*p)->destination]->from_city = from;} candidates.push(cities[(*p)->destination]);}} cities[from]->visited = true; if (cities[to]->visited) { return pair (cities[to]->total_fee, cities[to]->total_distance);} Else { return pair (INT_MAX, INT_MAX);}} Очередь с приоритетом для кандидатов Перебор по спискам смежности Присвоение min значений длины пути Для непосещённых вершин Добавляем вершину – «кандидата»

21 А ЛГОРИТМ Б ЕЛЛМАНА -Ф ОРДА Алгоритм Дейкстры - только в графе с положительными весами дуг. Для графа с отрицательными весами : как поступать с циклом с отрицательным весом? он делает большинство путей неопределными. Так, путь от V2 до V5 не определён, потому что можно попасть в петлю V3-V4-V1. Эту проблему решает алгоритм Беллмана- Форда

22 Р ЕАЛИЗАЦИЯ АЛГОРИТМА Б ЕЛЛМАНА -Ф ОРДА Аналогична реализации алгоритма Дейкстры Отличие: If (элемент есть в очереди) then она не включается повторно. КОД. If(find(candidates.begin(), candidates.end(), cities[(*p)- >destination)==candidates.end()) candidates.push(cities[(*p)->destination] Если очередь не содержит кандидата, то он добавляется

23 А ЦИКЛИЧЕСКИЕ ГРАФЫ Задача поиска кратчайшего пути связана с топологической сортировкой. Топологическая сортировка упорядочивает вершины в направленном ациклическом графе так, что If (имеется путь из u в v) then {v появляется после u в очерёдности.} Она невозможна, если граф имеет хотя бы 1 цикл. Описание: Находится вершина, не имеющая входных дуг. Она и все исходящие из неё дуги удаляются из графа.

24 А ЛГОРИТМ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ Все непройденные вершины с полустепенью захода 0 добавляются в очередь. Чтобы получить следующую вершину, мы извлекаем первый элемент из очереди. Когда полустепень захода элемента понижается до 0, он помещается в очередь

25 К ОД. vector > g; // граф int n; // число вершин vector used; vector ans; void dfs (int v) // процедура пометки непройденных вершин { used[v] = true; for (vector ::itetator i=g[v].begin(); i!=g[v].end(); ++i) if (!used[*i]) dfs (*i); ans.push_back (v); } void topological_sort (vector & result)// сама сортировка { used.assign (n, false); for (int i=0; i

26 И СПОЛЬЗОВАННАЯ ЛИТЕРАТУРА : Data Structures and Problem Solving with C++ [2nd Ed] [M. A. Weiss] [Addison Wesley] Полный справочник по С++, Г.Шилдт Дж. А. Андерсон, Дискретная математика и комбинаторика, М:2004.