Совершенный алгоритм. Графовые алгоритмы и структуры данных

Вторая книга (Графовые алгоритмы и структуры данных) из серии Совершенный алгоритм Тима Рафгардена является продолжением, по сути, единого цикла лекций. Автор не только сохранил стиль первой книги, но и часто ссылается на материал, который был в ней преподнесён. Стиль обоих книг я считаю очень удачным. А именно, детальное и всестороннее изложение небольшого количества тем доступным языком.

Снова, это не каталог решений, а именно лекции. Поэтому автор далеко не сразу дает готовые алгоритмы. По сути, автор рассказывает как к этим алгоритмам можно прийти. Либо пробуя разные варианты, либо постепенно улучшая решения. Так например, поиск кратчайшего пути:

1. Начинается с обхода в ширину.

2. Вводится модификация со взятием кратчайшего ребра при обходе.

3. Показывается, почему это не работает на отрицательных длинах, и доказывается, почему работает на неотрицательных.

4. Приводится анализ временной сложности.

5. Ставится задача быстрого поиска рёбер с минимальной длиной.

6. Вводится понятие кучи, необходимые на ней операции и их (желаемая) временная сложность.

7. Разбирается зачем и почему мы можем хранить в куче вершины, а не рёбра.

8. Приводятся детальные примеры где ещё такую структуру с такими операциями и их характеристиками можно было бы применить.

9. Даётся идея о реализации кучи в виде двоичного дерева.

10. Объясняется как её улучшить, перейдя к представлению в виде массива.

11. Детально иллюстрируется нарушение инварианта при вставке и удалении и поясняется как его восстановить.

Автор не разбирает как изначально собрать кучу за линейное время (можно посмотреть, например, и код, и анализ в An average case analysis of Floyd’s algorithm to construct heaps за авторством Ernst E. Doberkat от 1984 года), не приводит готовый код вставки и удаления, не приводит финальный готовый код реализации алгоритма поиска кратчайшего пути от начала до конца. Здесь это оставлено в виде задач. Но, если сравнивать с готовым решением в Грокаем алгоритмы, то, по крайней мере, в Совершенный алгоритм понятно откуда что взялось, почему и как; поиск минимумов с линейного заменён на логарифмический.

Очень скудно рассмотрено представление графов в виде матриц смежности. Недостаточно и информации чтобы с места написать балансировку деревьев или фильтр Блума. Но повторю вывод для первой части и здесь: если, чтение Кнута - это Труд, то Совершенный алгоритм - это просто интересное и увлекательное чтение.

Полное оглавление можно посмотреть на сайте издательства: тут.