![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Ббк 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
|