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




НазваниеГрафы их представление в stl отделение
Дата конвертации11.05.2013
Размер445 b.
ТипПрезентации


ГРАФЫ ИХ ПРЕДСТАВЛЕНИЕ В 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, то просмотр окончен)

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









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



Похожие:

Графы их представление в stl отделение iconСтандартная библиотека шаблонов stl stl (Standard Template Library) является частью стандарта C++
В каждом классе-контейнере определен набор методов для работы с контейнером, причем все контейнеры поддерживают
Графы их представление в stl отделение iconЛекции по курсу «Алгоритмизация и программирование» Лекция 14. Графы и их представление. Основные алгоритмы на графах

Графы их представление в stl отделение iconГу мрнц рамн отдел лазерной и фотодинамической терапии Отделение лучевого и хирургического лечения заболеваний торакальной области Отделение эндоскопии

Графы их представление в stl отделение iconОтделение фортепиано 7-8 лет Отделение народных инструментов 5-6 лет
Муниципальное Бюджетное Образовательное Учреждение Дополнительного образования Детей «Петровская Детская Школа Искусств» Башмаковского...
Графы их представление в stl отделение iconЛекция 18 Раскраска графов Эйлеровы графы Гамильтоновы графы Раскраска графов
Справедливо и обратное, любое такое расписание определяет правильную раскраску графа G. Следовательно, кратчайшее время необходимое...
Графы их представление в stl отделение iconЗаседание: Финансирование и модели управления школой Примеры из Соединенных Штатов Америки Конференция по инклюзивному образованию для детей с ограниченными возможностями
Организаторы: Региональное отделение юнисеф для стран цве/снг и страновое отделение юнисеф в Российской Федерации
Графы их представление в stl отделение iconГрафы

Графы их представление в stl отделение iconЛекция 2 Графы

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

Графы их представление в stl отделение iconГрафы, Планарность, Триангуляция, Делоне, Сетки Графы, Планарность, Триангуляция, Делоне, Сетки

Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница