Наверх

Роберт Седжвик, 2002 (Rus)
Фундаментальные алгоритмы на C++  |  Часть 5. Алгоритмы на графах

Эта книга посвящена глубокому исследованию всех основополагающих концепций и алгоритмов, которые, несомненно, относятся к категории «вечных». Тщательным образом проштудировав их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда. 
Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот лишь небольшой перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из наиболее эффективных языков программирования C++ лишний раз подчеркивает их популярность и «вечность». Подробно рассматривается широчайший спектр фундаментальных алгоритмов на графах, в числе которых: поиск в орграфах, неорграфах и сетях; построение минимальных остовных деревьев и кратчайших путей; вычисление потоков в сетях с различными характеристиками. Большое внимание уделяется рабочим характеристикам алгоритмов, а также их математическому выводу

Книгу можно использовать в качестве курса лекций (как студентами, так и преподавателями), справочного пособия или просто «романа», получая при этом ни с чем не сравнимое удовольствие


ОГЛАВЛЕНИЕ
Предисловие

ЧАСТЬ 5. АЛГОРИТМЫ НА ГРАФАХ 

ГЛАВА 17. СВОЙСТВА И ТИПЫ ГРАФОВ
   17.1. Глоссарий
   17.2. АТД графа
   17.3. Представление графа в виде матрицы смежности
   17.4. Представление графа в виде списка смежных вершин 
   17.5. Вариации, расширения и затраты 
   17.6. Генераторы графов 
   17.7. Простые, эйлеровы и гамильтоновы пути
   17.8. Задачи обработки графов 

ГЛАВА 18. ПОИСК НА ГРАФЕ
   18.4. Исследование лабиринта 
   18.2. Поиск в глубину
   18.3. Функции АТД поиска на графе
   18.4. Свойства лесов DFS
   18.5. Алгоритмы DFS
   18.6. Отделимость и бисвязность
   18.7. Поиск в ширину
   18.8. Обобщенный поиск на графах 
   18.9. Анализ алгоритмов на графах

ГЛАВА 19. ОРГРАФЫ И ОРИЕНТИРОВАННЫЕ АЦИКЛИЧЕСКИЕ ГРАФЫ
   19.1. Глоссарий и правила игры
   19.2. Анатомия поиска DFS в орграфах
   19.3. Достижимость и транзитивное замыкание
   19.4. Отношения эквивалентности и частичные порядки 
   19.5. Графы DAG
   19.6.Топологическая сортировка 
   19.7. Достижимость в графе DAG
   19.8. Сильные компоненты в орграфах
   19.9. Еще раз о транзитивном замыкании
   19.10. Перспективы 

ГЛАВА 20. МИНИМАЛЬНЫЕ ОСТОВНЫЕ ДЕРЕВЬЯ
  
20.1. Представления
   20.2. Принципы, положенные в основу алгоритмов построения дерева MST
   20.3. Алгоритм Прима и поиск по приоритету 
   20.4. Алгоритм Крускала 
   20.5. Алгоритм Борувки 
   20.6. Сравнения и усовершенствования
   20.7. Евклидово дерево MST 

ГЛАВА 21. КРАТЧАЙШИЕ ПУТИ
  
21.1. Основные принципы
   21.2. Алгоритм Дейкстры 
   21.3. Кратчайшие пути между всеми парами
   21.4. Кратчайшие пути в ациклических сетях 
   21.5. Евклидовы сети 
   21.6. Сведение 
   21.7. Отрицательные веса
   21.8. Перспективы 

ГЛАВА 22. ПОТОКИ В СЕТЯХ
  
22.1. Транспортные сети
   22.2. Алгоритм поиска максимального потока методом аугментального пути
   22.3. Алгоритмы определения максимальных потоков методом выталкивания превосходящего потока
   22.4. Сведение к максимальному потоку 
   22.5. Потоки минимальной стоимости
   22.6. Сетевой симплексный алгоритм 
   22.7. Сведение к задаче о потоке минимальной стоимости
   22.8. Перспективы 


ССЫЛКИ, ИСПОЛЬЗОВАННЫЕ В ПЯТОЙ ЧАСТИ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ