Ребер смежности вершин

Занимаемое пространство памяти (space) E V² V+E

Инициализировать пустой объект (initialize empty) 1 V² V

Копировать (сору) Е V² Е

Уничтожить (destroy) 1 V Е

Вставить ребра (insert edge) 1 1 1

Найти/удалить ребро (find/remove) E 1 V

Вершина v изолирована? (is v isolated?) E V 1

Путь от вершины и к вершине v? (path from u to v?) E lg* V V² V+E

Во многих случаях удается модифицировать представление графа таким образом, что простые операции становятся более эффективными, при этом принимаем меры против того, чтобы стоимость других простых операций не увеличивалась. Например, вхождение в таблице, соответствующее строке destroy и столбцу матрицы смежности, есть следствие (артефакт) выбора схемы раcпределения типа вектор векторов для двухмерных матриц (см. раздел 3.7). Нетрудно уменьшить эти затраты, сделав их постоянными (см. упражне­ние 17.25). С другой стороны, если ребра графа представляют собой достаточно сложные структуры, для которых элементы матрицы служат указателями, то операция destroy над матрицей смежности потребует затрат, пропорциональных V².

В силу того, что некоторые операции используются в типовых приложениях особен­но часто, подробно рассмотрим операции find edge (найти ребро) и remove edge (удалить реб­ро). В частности, операция find edge нужна нам для того, чтобы иметь возможность уда­лить или запретить включение параллельных ребер. Как следует из раздела 13.4, эти операции тривиальны, если мы пользуемся представлением графа в виде матрицы смеж­ности — нам достаточно всего лишь проверить или установить значение элемента матри­цы, который можно индексировать непосредственно. В то же время, как можно обеспе­чить эффективную реализацию этих операций в условиях представления графа в виде списка смежных вершин? В языке C++ можно воспользоваться библиотекой STL; здесь мы описываем базовые механизмы, чтобы получить представление о проблемах обеспе­чения эффективности. Один из подходов описан ниже, другой подход упоминается в уп­ражнении 17.50. Оба подхода основаны на использовании реализаций таблицы символов. Например, если мы используем реализации динамической хэш-таблицы (см. раздел 14.5), оба подхода требуют памяти, пропорциональной Е, и позволяют выполнять и ту и другую операции за постоянное время (в среднем, с амортизацией расходов на реализацию).

В частности, чтобы реализовать операцию find edge, когда мы используем списки смеж­ных вершин, можно воспользоваться вспомогательной таблицей соответствия символов для ребер. Мы можем присвоить ребру v-w целочисленный ключ v*V+w и задействовать функцию тар из библиотеки STL или любую реализацию таблицы символов, описание которых приводится в части 4. (Для неориентированных графов можно присваивать одни и те же ключи ребрам v-w и w-v.) Мы можем вставить каждое ребро в таблицу символов, предварительно проверив, не было ли оно включено раньше. Мы можем остановить свой выбор либо на том, чтобы блокировать включение параллельных ребер (см. упражнение