ГРАФЫ ИХ ПРЕДСТАВЛЕНИЕ В STL Отделение программной инженерии группа 271 ПИ Антонова Н.А.
ГРАФ
БИБЛИОТЕКА 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, то просмотр окончен) Структура данных – стек
|