Ббк 32. 973. 2

Translation copyright © 2002 by DIASOFT LTD. (Original English language title from Proprietor's edition of the Work)

Original English language title: Algorithms in C++, Parts 5: Graph Algorithms, Third Edition by Robert Sedgewick, Copyright © 2002, All rights reserved

Published by arrangement with the original publisher, ADDISON WESLEY LONGMAN, a Pearson Education Company.

Лицензия предоставлена издательством Addison Wesley Longman. (Pearson Education, Inc.)

Все права зарезервированы, включая право на полное или частичное воспроизведение в какой бы то ни было форме.

Материал, изложенный в данной книге многократно проверен. Но поскольку вероятность тех­нических ошибок все равно остается, издательство не может гарантировать абсолютную точ­ность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги.

Все торговые знаки, упомянутые в настоящем издании, зарегистрированы. Случайное непра­вильное использование или пропуск торгового знака или названия его законного владельца не должно рассматриваться как нарушение прав собственности.

ISBN 5-93772-054-7 (рус.) © Перевод на русский язык. ISBN 0-201-36118-3 (англ.)© Pearson Education, Inc., 2002.

© Оформление. ООО " ДиаСофnЮП"

Гигиеническое заключение № 77.99.6953.11.438.2.99 ОТ 04.02.1999

Оглавление

Предисловие.............................................................................. 7

Часть 5. Алгоритмы на графах.................................................... 17

Глава 17. Свойства и типы графов.............................................. 18

Глоссарий................................................................................................................................... 22

АТД графа................................................................................................................................... 31

Представление графа в виде матрицы смежности...................................................... 38

Представление графа в виде списка смежных вершин............................................ 44

Вариации, расширения и затраты.................................................................................... 49

Генераторы графов................................................................................................................. 58

Простые, эйлеровы и гамильтоновы пути..................................................................... 69

Задачи обработки графов..................................................................................................... 83

Глава 18. Поиск на графе............................................................ 93

Исследование лабиринта..................................................................................................... 94

Поиск в глубину...................................................................................................................... 99

Функции АТД поиска на графе...................................................................................... 103

Свойства лесов DFS.............................................................................................................. 109

Алгоритмы DFS...................................................................................................................... 117

Отделимость и бисвязность.............................................................................................. 123

Поиск в ширину.................................................................................................................... 132

Обобщенный поиск на графах........................................................................................ 141

Анализ алгоритмов на графах......................................................................................... 150