Графы их представление в stl отделение

ГРАФЫ ИХ ПРЕДСТАВЛЕНИЕ В STL

• Отделение

• программной инженерии

• группа 271 ПИ

• Антонова Н.А.

ГРАФ

• G =

БИБЛИОТЕКА STL

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

КОНТЕЙНЕРЫ

• Последовательные Ассоциативные

• (линейный список) (ключ – значение)

КОНТЕЙНЕРЫ

• VECTOR – динамический массив

• size() – возвращает текущий размер вектора
• begin() – возвращает итератор, установленный на начало вектора
• end() - возвращает итератор, установленный на конец вектора
• push_back() – записывает значение в конец вектора
• insert() – записывает значение непосредственно перед элементом, на который ссылается итератор
• erase() – удаляет элемент из вектора
• …

КОНТЕЙНЕРЫ

• VECTOR – динамический массив

• size() – возвращает текущий размер вектора
• begin() – возвращает итератор, установленный на начало вектора
• end() - возвращает итератор, установленный на конец вектора
• push_back() – записывает значение в конец вектора
• insert() – записывает значение непосредственно перед элементом, на который ссылается итератор
• erase() – удаляет элемент из вектора
• …

КОНТЕЙНЕРЫ

• SET – упорядоченные уникальные значения;

• MAP – ассоциативный контейнер:

• уникальный ключ – значение

КОНТЕЙНЕРЫ

• MAP – ассоциативный контейнер:

• уникальный ключ – значение

КОНТЕЙНЕРЫ

• MULTIMAP – ключ может иметь несколько значений

• PRIORITY_QUEUE – очередь с приоритетами

СМЕЖНОСТЬ и ИНЦИДЕНТНОСТЬ

• Вершины, соединенные дугой, называются смежными

• Дуги, имеющие общую вершину, также называются смежными

• Дуга и любая из ее вершин называются инцидентными

ПРЕДСТАВЛЕНИЕ ГРАФОВ

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

• Матрица инциденций

• Структуры смежности

• Массив дуг

МАТРИЦА СМЕЖНОСТИ

• Это двумерный массив размером NxN, где

• N – мощность множества вершин V (|V|=N)

МАТРИЦА ИНЦИДЕНЦИЙ

• Это двумерный массив размером NxМ, где

• N – мощность множества вершин V (|V|=N), М – мощность множества ребер (|E|=M)

СТРУКТУРА СМЕЖНОСТИ

• Это одномерный массив размером N, где

• N – мощность множества вершин V (|V|=N). Элемент массива – указатель на начало списка, где храниться перечень вершин, смежных с рассматриваемой

МАССИВ ДУГ

• Это двумерный массив размером Мx2,

• где М – мощность множества ребер Е (|Е|=М)

Использование в прикладных задачах

• Географические карты и маршруты

• Расписания (scheduling)

• Web (гипертекст)

• Сети (networks) и т.д.

ПОИСК КРАТЧАЙШЕГО ПУТИ

ПУТЬ

ПРЕДСТАВЛЕНИЕ

АЛГОРИТМ ДЕЙКСТРЫ

ОСНОВНЫЕ АЛГОРИТМЫ НА ГРАФАХ

Breadth-First Search Поиск в ширину

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

Рассматриваются все вершины, связанные с текущей

• Рассматриваются все вершины, связанные с текущей

• Выбирается та вершина, которая раньше была рассмотрена

• Структура данных – очередь

Depth-First Search Поиск в глубину

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

Поиск начинается с некоторой фиксированной вершины v

• Поиск начинается с некоторой фиксированной вершины v

• Рассматривается вершина u, смежная с v

• Если нет вершин, смежных с текущей, возврат к предыдущей (если эта вершина – v, то просмотр окончен)

• Структура данных – стек

• СПАСИБО ЗА ВНИМАНИЕ!