Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Смежных вершин
|
|
Стандартное представление графа, которому обычно отдают предпочтение, когда граф не относится к числу насыщенных, называется представлением в виде списков смежных вершин (adjacency-lists), в рамках которого мы отслеживаем все вершины, соединенные с каждой вершиной, включенной в связанный список этой вершины. Мы поддерживаем вектор списков, так что достаточно указать вершину, чтобы получить немедленный доступ к ее списку; мы используем связные списки для того, чтобы ввести новое ребро за постоянное время.
Программа 17.9 представляет собой реализацию интерфейса АТД из программы 17.1, основанную на рассматриваемом подходе, а на рис. 17.10 приводится соответствующий пример. Чтобы добавить в это представление графа ребро, соединяющее вершину v с w, мы добавляем w в список смежности вершины v и v в список смежности вершины w. Таким образом, мы можем выполнить ввод новых ребер за постоянное время, однако используемое при этом общее пространство памяти пропорционально числу вершин плюс число ребер (в отличие от пропорциональности квадрату числа вершин, что имеет место в случае представления графа в виде матрицы смежности). Что касается неориентированных графов, то ребра опять фигурируют в двух различных местах, ибо ребро, соединяющее вершину v c w, представлено как узлы в обоих списках смежных вершин. Оба включения обязательны, в противном случае мы не сможем толково ответить на такие простые вопросы как: " Какие вер-
РИСУНОК 17.10. СТРУКТУРА ДАННЫХ СПИСКА СМЕЖНЫХ ВЕРШИН
Данный рисунок отображает представление графа, приведенного на рис. 17.1, в виде массива связных списков. Использованное для этого представления пространство памяти пропорционально сумме числа вершин и числа ребер. Чтобы найти индексы вершин, связанных с заданной вершиной v, мы просматриваем v-ю позицию этого массива, которая содержит указатель на связный список, содержащий один узел для каждой вершины, соединенной с v. Порядок, в котором узлы расположены в списках, зависит от метода, использованного для построения этих списков.