Смежных вершин

Стандартное представление графа, которому обыч­но отдают предпочтение, когда граф не относится к числу насыщенных, называется представлением в виде списков смежных вершин (adjacency-lists), в рамках кото­рого мы отслеживаем все вершины, соединенные с каждой вершиной, включенной в связанный список этой вершины. Мы поддерживаем вектор списков, так что достаточно указать вершину, чтобы получить не­медленный доступ к ее списку; мы используем связ­ные списки для того, чтобы ввести новое ребро за по­стоянное время.

Программа 17.9 представляет собой реализацию интерфейса АТД из программы 17.1, основанную на рассматриваемом подходе, а на рис. 17.10 приводится соответствующий пример. Чтобы добавить в это пред­ставление графа ребро, соединяющее вершину v с w, мы добавляем w в список смежности вершины v и v в список смежности вершины w. Таким образом, мы можем выполнить ввод новых ребер за постоянное время, однако используемое при этом общее про­странство памяти пропорционально числу вершин плюс число ребер (в отличие от пропорциональности квадрату числа вершин, что имеет место в случае пред­ставления графа в виде матрицы смежности). Что ка­сается неориентированных графов, то ребра опять фи­гурируют в двух различных местах, ибо ребро, соединяющее вершину v c w, представлено как узлы в обоих списках смежных вершин. Оба включения обя­зательны, в противном случае мы не сможем толково ответить на такие простые вопросы как: " Какие вер-

РИСУНОК 17.10. СТРУКТУРА ДАННЫХ СПИСКА СМЕЖНЫХ ВЕРШИН

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