Часть 5. Алгоритмы на графах. 17.49), либо на ведении дублированных записей в таблице соответствия символов, фик­сирующих параллельные ребра (см

17.49), либо на ведении дублированных записей в таблице соответствия символов, фик­сирующих параллельные ребра (см. упражнение 17.50). В настоящем контексте основной интерес к этому методу вызывается тем, что он делает возможной такую реализацию опе­рации find edge, которая обеспечивает ее выполнение за постоянное время для представ­ления графа в виде списка смежных вершин.

Чтобы иметь возможность удалять ребра, в записи таблицы символов для каждого реб­ра необходим указатель на его представление в структуре списка смежных вершин. Но даже этой информации недостаточно для того, чтобы дать возможность удалять ребра за постоянное время, если только списки не являются дважды связными (см. раздел 3.4). Более того, в случае неориентированных графов нельзя ограничиваться только удалени­ем узла из списка смежных вершин, поскольку каждое ребро содержится в двух различ­ных списках смежных вершин. Один из способов устранения этого затруднения заклю­чается в том, чтобы поместить оба указателя в таблицу соответствия символов; другой предусматривает связывание двух узлов, соответствующих конкретному ребру (см. упраж­нение 17.46). Какое бы из двух этих решений мы не выбрали, мы получаем возможность удалить ребро за постоянное время.

Удаление вершин требует больших затрат. В представлении графа в виде матрицы смежности мы, по существу, должны удалить из матрицы соответствующие строку и стол­бец, что требует не меньших затрат, чем построение новой матрицы смежности меньше­го размера (хотя в этом случае эти издержки можно уменьшить, если воспользоваться тем же механизмом, который применяется при работе с динамическими хэш-таблицами). Если мы используем представление графа в виде списков смежных вершин, то сразу видим, что недостаточно только удалить узлы из списка смежных вершин той или иной вершины, поскольку каждый узел списка смежных вершин определяет другую вершину, список смежных вершин которой мы обязаны просмотреть, чтобы удалить другой узел, который представляет то же ребро. В соответствии с изложенным в предыдущем параграфе, если мы хотим удалить вершину за время, пропорциональное числу вершин К, необходимо обеспечить поддержку удаления ребра за постоянное время, а для этого потребуются до­полнительные связи.

Здесь мы не будем останавливаться на реализации этих операций в силу того, что они представляют собой простые упражнения по программированию, в рамках которых ис­пользуются базовые технологии, описанные в части 1; в силу того, что библиотека STL содержит реализации, которыми мы можем пользоваться, поскольку поддержка сложных структур со множественными указателями в узле не оправдывается в типовых приложе­ниях обработки статических графов; и в силу того, что мы не хотим утонуть в трясине бесконечных уровней абстракций или в мелких деталях поддержки многочисленных ука­зателей при реализации алгоритмов обработки графов, которые без этого не могут их ис­пользовать. В главе 22 мы будем изучать реализации подобных структур, играющих важ­ную роль в мощных универсальных алгоритмах, изучение которых будет продолжаться в данной главе.

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