Алгоритмы на графах. Использование языка Python

От авторов....5
Глава 1. Структуры данных....9
Общие понятия....11
1. Списки....11
2. Списки со ссылками....12
3. Стеки и очереди....14
4. Двусторонняя очередь....17
5. Двоичные деревья....17
6. Структура данных «куча»....19
Реализации в Python....24
7. Списки и кортежи....24
8. Стеки и очереди на основе списков list....35
9. Очередь на основе списка со ссылками....39
10. Очередь по приоритету на основе кучи....41
Глава 2. Графы....43
1. Общие понятия и обозначения....45
2. Структуры данных для представления графов....51
3. Ввод данных, которые задают граф....57
4. Изоморфизм графов....60
5. Поиск в ширину....62
6. Расстояние между вершинами....68
7. Выявление связных компонент графа....68
4 Оглавление
8. Диаметр, радиус и центр графа....70
9. Распознавание двудольного графа....74
10. Поиск в глубину....77
11. Остовное дерево наименьшего веса....88
12. Фундаментальное множество циклов в графе....101
13. Эйлеровы циклы....105
14. Гамильтоновы циклы....110
Глава 3. Ориентированные графы....117
1. Топологическая сортировка вершин орграфа....119
2. Все циклы в ориентированном графе....129
3. Поиск кратчайших путей....133
4. Кратчайшие пути между всеми парами вершин ....142
5. Транзитивное замыкание орграфа....149
6. Максимальный поток в транспортной сети....153
Приложения....169
А. Справочные сведения из языка Python....171
Б. Рекурсия....187
В. Порождение перестановок....197
Г. Построение изображения графа....202
Д. Трудоемкость алгоритмов....208
Е. Справочные сведения о математиках,
упоминаемых в книге....217
Рекомендуемая литература....219

В настоящей книге достаточно популярно излагаются базовые алгоритмы на графах вместе с их реализациями на языке Python. Материал иллюстрирован большим числом примеров и рисунков, способствующих его усвоению.
Книга адресована прежде всего учителям информатики общеобразовательных учреждений (школ, гимназий, лицеев) и студентам соответствующих специальностей педагогических вузов, а также всем, кто интересуется прикладной теорией графов и программированием.