Алгоритмы на графах. Использование языка 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. Материал иллюстрирован большим числом примеров и рисунков, способствующих его усвоению.
 Книга адресована прежде всего учителям информатики общеобразовательных учреждений (школ, гимназий, лицеев) и студентам соответствующих специальностей педагогических вузов, а также всем, кто интересуется прикладной теорией графов и программированием.