![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. 17.49), либо на ведении дублированных записей в таблице соответствия символов, фиксирующих параллельные ребра (см
Чтобы иметь возможность удалять ребра, в записи таблицы символов для каждого ребра необходим указатель на его представление в структуре списка смежных вершин. Но даже этой информации недостаточно для того, чтобы дать возможность удалять ребра за постоянное время, если только списки не являются дважды связными (см. раздел 3.4). Более того, в случае неориентированных графов нельзя ограничиваться только удалением узла из списка смежных вершин, поскольку каждое ребро содержится в двух различных списках смежных вершин. Один из способов устранения этого затруднения заключается в том, чтобы поместить оба указателя в таблицу соответствия символов; другой предусматривает связывание двух узлов, соответствующих конкретному ребру (см. упражнение 17.46). Какое бы из двух этих решений мы не выбрали, мы получаем возможность удалить ребро за постоянное время. Удаление вершин требует больших затрат. В представлении графа в виде матрицы смежности мы, по существу, должны удалить из матрицы соответствующие строку и столбец, что требует не меньших затрат, чем построение новой матрицы смежности меньшего размера (хотя в этом случае эти издержки можно уменьшить, если воспользоваться тем же механизмом, который применяется при работе с динамическими хэш-таблицами). Если мы используем представление графа в виде списков смежных вершин, то сразу видим, что недостаточно только удалить узлы из списка смежных вершин той или иной вершины, поскольку каждый узел списка смежных вершин определяет другую вершину, список смежных вершин которой мы обязаны просмотреть, чтобы удалить другой узел, который представляет то же ребро. В соответствии с изложенным в предыдущем параграфе, если мы хотим удалить вершину за время, пропорциональное числу вершин К, необходимо обеспечить поддержку удаления ребра за постоянное время, а для этого потребуются дополнительные связи. Здесь мы не будем останавливаться на реализации этих операций в силу того, что они представляют собой простые упражнения по программированию, в рамках которых используются базовые технологии, описанные в части 1; в силу того, что библиотека STL содержит реализации, которыми мы можем пользоваться, поскольку поддержка сложных структур со множественными указателями в узле не оправдывается в типовых приложениях обработки статических графов; и в силу того, что мы не хотим утонуть в трясине бесконечных уровней абстракций или в мелких деталях поддержки многочисленных указателей при реализации алгоритмов обработки графов, которые без этого не могут их использовать. В главе 22 мы будем изучать реализации подобных структур, играющих важную роль в мощных универсальных алгоритмах, изучение которых будет продолжаться в данной главе. Для ясности описания и с целью разработки реализаций, представляющих для нас интерес, мы воспользуемся простейшей из подходящих представлений. Вообще говоря, мы стремимся использовать структуры данных, которые лучше всего подходят для решения имеющихся задач. Многие программисты придерживаются этого вида минимализма как нечто само собой разумеющееся, понимая, что соблюдение принципа целостности струк-
|