![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17. Свойства и типы графов. функций не представляет каких-либо трудностей (см
Когда в качестве имен вершин графа используются обозначения, отличные от целых чисел, то (как и в случае матриц смежности) две разные программы могут связывать имена вершин с целыми числами в диапазоне от 0 до V— 1 двумя различными способами, приводящими к образованию двух различных структур списка смежных вершин (см., например, программу 17.15). Мы не можем рассчитывать на то, что сумеем определить, представляют ли различные структуры один и тот же граф, ввиду сложности проблемы изоморфизма графов. Более того, существует множество представлений графа с заданным числом вершин в виде списков смежных вершин даже при заданной нумерации вершин. Не важно, в каком порядке появляются ребра в списке смежных вершин, структура списка смежных вершин представляет один и тот же граф (см. упражнение 17.33). Полезно знать об этом свойстве списков смежных вершин, поскольку порядок, в котором ребра появляются в списках смежные вершины, влияет, в свою очередь, на порядок, в котором ребра обрабатываются алгоритмами. Это значит, что структура списка смежных вершин определяет, под каким углом зрения используемые нами алгоритмы видят сам граф. И хотя алгоритм должен дать правильный ответ вне зависимости от того, в каком порядке расположены ребра в списке смежных вершин, он должен прийти к правильному ответу в условиях различных последовательностей вычислений, обусловленных различными видами упорядочения ребер. Если алгоритм не обязательно должен проверять все ребра, образующие граф, это обстоятельство может повлиять на продолжительность выполнения данной операции. Кроме того, если имеются несколько правильных решений, то различные упорядочения входных данных могут привести к различным выходным результатам. Основное преимущество представления графа в виде списка смежных вершин перед представлением в виде матрицы смежности заключается в том, что на его реализацию затрачивается пространство памяти, пропорциональное V + Е, а не V2, как в случае представления в виде матрицы смежности. Основной недостаток этого представления состоит в том, что проверка существования конкретных ребер может потребовать времени, пропорционального V, в противовес постоянному времени в случае матрицы смежности. Эти различия приводят, главным образом, к различию в использовании связных списков и векторов для представления множеств вершин, инцидентных каждой вершине. Таким образом, мы снова убеждаемся в том, что понимание основных свойств связных структур данных и векторов критично для построения реализаций АТД графа. Наш интерес к такому различию в производительности обусловливается тем фактом, что мы хотим избежать реализаций, эффективность которых падает до недопустимого уровня в условиях, когда от АТД требуется выполнение широкого спектра операций. В разделе 17.5
|