Алгоритм
<<  Алгоритм решения расчетных задач по химии Алгоритм выполнения заданий С  >>
Алгоритмы на графах
Алгоритмы на графах
Определения
Определения
Структура библиотеки STL
Структура библиотеки STL
3 возможных представления
3 возможных представления
Используемые классы библиотеки
Используемые классы библиотеки
Представление графа: вариант1
Представление графа: вариант1
Представление графа: вариант 2
Представление графа: вариант 2
Представление графа : вариант 3
Представление графа : вариант 3
Обход в ширину
Обход в ширину
Обход в ширину:код
Обход в ширину:код
Обход в глубину
Обход в глубину
Обход в глубину:код
Обход в глубину:код
Алгоритм Дейкстры
Алгоритм Дейкстры
Определение алгоритма
Определение алгоритма
Начальные стадии алгоритма
Начальные стадии алгоритма
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины
Все соседи вершины 1 проверены
Все соседи вершины 1 проверены
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь
Повторяем аналогичные действия для остальных вершин
Повторяем аналогичные действия для остальных вершин
Код
Код
Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда
Реализация алгоритма Беллмана-Форда
Реализация алгоритма Беллмана-Форда
Ациклические графы
Ациклические графы
Алгоритм топологической сортировки
Алгоритм топологической сортировки
Код
Код
Использованная литература:
Использованная литература:

Презентация: «Алгоритмы на графах». Автор: Светик. Файл: «Алгоритмы на графах.ppt». Размер zip-архива: 914 КБ.

Алгоритмы на графах

содержание презентации «Алгоритмы на графах.ppt»
СлайдТекст
1 Алгоритмы на графах

Алгоритмы на графах

Реализация в библиотеке STL.

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

2 Определения

Определения

Будем рассматривать задачу в терминах ориентированных графов. Граф – конечное множество V, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение R и выделено множество E двухэлементных подмножеств V, определяемое как {a,b}€ E тогда и только тогда, когда (a,b) € R и a ? b, и (b,a) не входит в Е. Вес – параметр дуги, длина дуги. Путь – сумма длин входящих в него дуг. Полустепенью исхода(захода) называется число исходящих (входящих) дуг. Две вершины – смежные, если они соединены дугой. Длина пути(во взвешенном графе) – ? весов дуг графа. Цикл – путь, который начинается и заканчивается в одной той же вершине и содержит как минимум 1 дугу. Ациклическим считается граф, не содержащий ни одного цикла. В разреженном графе m<<n2, где m – число дуг, n – число вершин. Иначе , m=c*n, где с – константа, с?4. В насыщенном графе m?n2 или m ? c*n2 , где с – константа, с<1.

3 Структура библиотеки STL

Структура библиотеки STL

Библиотека содержит пять основных видов компонентов: * алгоритм (algorithm): определяет вычислительную процедуру. * контейнер (container): управляет набором объектов в памяти. * итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера. * функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами. * адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

4 3 возможных представления

3 возможных представления

Матрица смежности(vector<vector<int> >) для насыщенного графа Структура смежности(vector< list<int> > ) Для разреженного графа Представление в форме map Для представления при входе

5 Используемые классы библиотеки

Используемые классы библиотеки

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

Для ввода-вывода

Для представления графа в виде матрицы

Для создания очередей(например, для хранения вершин)

Для создания строк

Для определения функторов

Для создания списков

6 Представление графа: вариант1

Представление графа: вариант1

Если граф взвешенный: Представление графа в виде массива дуг с помощью STL map. Дуге(из 2-х вершин) сопоставляется её вес. Пример: представление визуальное и в форме map

Пример: map<string, list<int> >::iterator it; // Создание итератора для перехода по map Int i =10; it->first.push_back(i);// первая вершина

Используем это представление для упорядочения графа на входе в программу

7 Представление графа: вариант 2

Представление графа: вариант 2

Если граф насыщенный: Используется двумерная матрица смежности A. Для дуги (vi,wj) с весом ci,j A[i][j] = ci,j Несуществующие дуги – значение «бесконечность» В STL представляется как vector<vector<int> >

8 Представление графа : вариант 3

Представление графа : вариант 3

Если граф разреженный и связный: Используется структура смежности: массив списков. vector< list<int> >

Вес соответствующей дуги

№ Вершины

vector<list<int>>::iterator it = new interator;

Хранится вектор вершин, которым сопоставлены списки номеров вершин, смежных с ними.

Список смежных вершин

Будем представлять граф именно так.

9 Обход в ширину

Обход в ширину

Алгоритм: Выбираем непройденную вершину. Проверяем все рёбра и запоминаем непройденные вершины на их концах. Выбираем непройденную вершину и повторяем действия.

10 Обход в ширину:код

Обход в ширину:код

Вершина представлена парой значений: номер и посещение

Очередь реализована как deque

Текущая вершина – первая в очереди кандидатов

Проверка непустоты очереди

Выход из цикла, если все вершины просмотрены

typedef pair<int, bool> vertex; typedef multimap<int, int>::iterator edgesIt; vector<vertex> vertices; multimap<int, int> edges; deque<vertex> q; while(1) { current = q.front(); q.pop_front(); vector<vertex>::iterator vIt = find(vertices.begin(), vertices.end(), vertex(current.first, current.second)); (*vIt).second = true; cout << "Visited: " << (*vIt).first << endl; pair<edgesIt, edgesIt> rangeIt = edges.equal_range(current.first); for(edgesIt eIt = rangeIt.first; eIt != rangeIt.second; eIt++) { if((find(vertices.begin(), vertices.end(), vertex((*eIt).second, true)) == vertices.end()) && (find(q.begin(), q.end(), vertex((*eIt).second, false)) == q.end())) { push_back(vertex((*eIt).second, false)); cout << "To deque: " << (*eIt).second << endl; } } if(q.empty()) break; } cout << "End." << endl; return EXIT_SUCCESS;}

11 Обход в глубину

Обход в глубину

Алгоритм: Выбираем непройденную вершину Выбираем 1 из непройденных смежных вершин Если нет смежных непройденных вершин, то помечаем вершину пройденной и возвращаемся в запомненную вершину.

12 Обход в глубину:код

Обход в глубину:код

Рекурсивная реализация: vector < vector<int> > g; // граф int n; // число вершин vector<char> used; void dfs (int v) { used[v] = true; for (vector<int>::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-й вершины

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины

— 3-й и 6-й.

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

17 Все соседи вершины 1 проверены

Все соседи вершины 1 проверены

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

18 Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь

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

19 Повторяем аналогичные действия для остальных вершин

Повторяем аналогичные действия для остальных вершин

20 Код

Код

priority_queue<int, vector<int>, Cheapest> candidates; while(1) { for(list<int>::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<int,int>(cities[to]->total_fee, cities[to]->total_distance);} Else { return pair<int,int>(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 < vector<int> > g; // граф int n; // число вершин vector<bool> used; vector<int> ans; void dfs (int v) // процедура пометки непройденных вершин { used[v] = true; for (vector<int>::itetator i=g[v].Begin(); i!=G[v].End(); ++i) if (!Used[*i]) dfs (*i); ans.Push_back (v); } void topological_sort (vector<int> & result)// сама сортировка { used.Assign (n, false); for (int i=0; i<n; ++i) if (!Used[i]) dfs (i); result = ans; }

26 Использованная литература:

Использованная литература:

Data Structures and Problem Solving with C++ [2nd Ed] [M. A. Weiss] [Addison Wesley] Полный справочник по С++, Г.Шилдт http://www.rsdn.ru/ http://e-maxx.ru/algo/ Дж. А. Андерсон, Дискретная математика и комбинаторика, М:2004.

«Алгоритмы на графах»
http://900igr.net/prezentacija/informatika/algoritmy-na-grafakh-246158.html
cсылка на страницу

Алгоритм

31 презентация об алгоритме
Урок

Информатика

130 тем
Слайды