Глава 17. Свойства и типы графов. шины являются смежными с вершиной v? Программа 10.7 реализует итератор, который дает ответ клиентам

шины являются смежными с вершиной v? " Программа 10.7 реализует итератор, который дает ответ клиентам, задающим подобного рода вопросы, за время, пропорциональное числу таких вершин.

Реализации в программах 17.9 и 17.10 являются низкоуровневыми. В качестве альтер­нативы можно воспользоваться функцией list библиотеки STL, чтобы реализовать каждый связный список (см. упражнение 17.30). Недостаток такого подхода заключается в том, что реализации функции list библиотеки STL требуют поддержки гораздо большего чис­ла операций, чем требуется, а это обычно влечет за собой непроизводительные затраты, которые могут неблагоприятно повлиять на все разрабатываемые нами алгоритмы (см. упражнение 17.31). В самом деле, все наши алгоритмы на графах используют интерфейс АТД Graph, следовательно, эта реализация служит подходящим местом для инкапсуляции всех низкоуровневых операций, благодаря чему достигается требуемая эффективность и не затрагиваются другие программы. Другое преимущество использования представления графа в виде связного списка заключается в том, что оно предлагает конкретную базу для оценки рабочих характеристик наших приложений.

Еще одним важным фактором, который следует учесть, является тот факт, что реали­зация в программах 17.9 и 17.10, в основу которой положены связные списки, не полна по причине отсутствия деструктора и конструктора копирования. Для многих приложе­ний это обстоятельство приводит к неожиданным результатам или острым проблемам, обусловленным снижением производительности. Эти функции представляют собой пря­мое расширение функций, используемых в реализации очереди первого класса в про­грамме 4.22 (см. упражнение 17.29). На протяжении всей книги мы полагаем, что объек­ты SparceMultiGRAPH содержат их. Использование функции list из библиотеки STL вместо однонаправленных списков обладает несомненным преимуществом, которое зак­лючается в том, что отпадает необходимость в дополнительном программном коде, по­скольку теперь соответствующий деструктор и конструктор копирования определяются автоматически. Например, объекты DenseGRAPH, построенные в программе 17.7, дол­жным образом порождаются и уничтожаются клиентскими программами, которые мани­пулируют ими, так как они построены на базе объектов из библиотеки STL.