|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[150] 23.1. Основные алгоритмы на графах В этой главе описаны основные способы представления графов и алгоритмы обхода графов. Обходя граф, мы двигаемся по рёбрам и проходим все вершины. При этом накапливается довольно много информации, которая полезна для дальнейшей обработки графа, так что обход графа входит как составная часть во многие алгоритмы. В разделе 23.1 обсуждаются два основных способа представления графа в памяти компьютера - с помощью списков смежных вершин и с помощью матрицы смежности. Раздел 23.2 описывает алгоритм поиска в ширину и соответствующее этому алгоритму дерево. В разделе 23.3 рассматривается другой порядок обхода вершин и доказываются свойства соответствующего алгоритма (называемого поиском в глубину). В разделе 23.4 мы используем разработанные методы для решения задачи о топологической сортировке ориентированного графа без циклов. Другое применение поиска в глубину (отыскания сильно связных компонент ориентированного графа) описано в разделе 23.5. 23.1.1. Представление графов Есть два стандартных способа представить граф G = (V, Е) - как набор списков смежных вершин или как матрицу смежности. Первый обычно предпочтительнее, ибо даёт более компактное представление для разреженных (sparse) графов - тех, у которых \Е\ много меньше \V\2. Большинство издагаемых нами алгоритмов используют именно это представление. Однако в некоторых ситуациях удобнее пользоваться матрицей смежности - например, для плотных (dense) графов, у которых \Е\ сравнимо с \V\2. Матрица смежности позволяет быстро определить, соединены ли две данные вершины ребром. Два алгоритма отыскания кратчайших путей для всех пар вершин, описанные в главе 26, используют представление графа с помощью матрицы смежности. Представление графа G = (V, Е) в виде списков смежных вершин (adjancency-list representation) использует массив Adj из \V\ списков - по одному на вершину. Для каждой вершины и £ V список смежных вершин Аф[и] содержит в произвольном порядке (указатели на) все смежные с ней вершины (все вершины v, для которых (и, v) G Е). На рис. 23.1 (Ь) показано представление неориентированного графа рис. 23.1 (а) с помощью списков смежных вершин. Аналогичное представление для ориентированного графа рис. 23.2 (а) изображено на рис. 23.2 (Ь). Рис. 23.1 23.1 Два представления неориентированного графа, (а) Неориентированный граф G с 5 вершинами и 7 рёбрами. (Ь) Представление этого графа с помощью списков смежных вершин, (с) Представление этого графа в виде матрицы смежности. Рис. 23.2 23.2 Два представления ориентированного графа, (а) Ориентированный граф G с 6 вершинами и 8 рёбрами. (Ь) Представление этого графа с помощью списков смежных вершин, (с) Представление этого графа в виде матрицы смежности. Для ориентированного графа сумма длин всех списков смежных вершин равна общему числу рёбер: ребру (и, v) соответствует элемент v списка Аф[и]. Для неориентированного графа эта сумма равна удвоенному числу рёбер, так как ребро (и, v) порождает элемент в списке смежных вершин как для вершины и, так и для v. В обоих случаях количество требуемой памяти есть 0(max(V,E)) = 0(V + E). Списки смежных вершин удобны для хранения графов с весами (weighted graphs), в которых каждому ребру приписан некоторый вещественный вес (weight), то есть задана весовая функция (weight function) w : Е -> Ж. В этом случае удобно хранить вес w(u,v) ребра (и, v) £ Е вместе с вершиной v в списке вершин, смежных с и. Подобным образом можно хранить и другую информацию, связанную с графом. Недостаток этого представления таков: если мы хотим узнать, есть ли в графе ребро из и в v, приходится просматривать весь список Аф[и] в поисках v. Этого можно избежать, представив граф в виде матрицы смежности - но тогда потребуется больше памяти. При использовании матрицы смежности мы нумеруем вершины графа (V, Е) числами 1,2,... ,\V\ и рассматриваем матрицу А = (aij) размера \V\ X \V\, для которой Г 1, если (г, j) £ Е, [ 0 в противном случае На рис. 23.1 (с) и 23.2 (с) показаны матрицы смежности неориентированного и ориентированного графов рис. 23.1 (а) и 23.2 (а) соответственно. Матрица смежности требует Q(V2) памяти независимо от количества ребер в графе. Для неориентированного графа матрица смежности симметрична относительно главной диагонали (как на рис. 3.1(c)), поскольку (и, v) и (v, и) - это одно и то же ребро. Другими словами, матрица смежности неориентированного графа совпадает со своей транспонированной (transpose). (Транспонированием называется переход от матрицы А = (aij) к матрице АТ = (afj), для которой aj- = dji. Благодаря симметрии достаточно хранить только числа на главной диагонали и выше нее, тем самым мы сокращаем требуемую память почти вдвое. Как и для списков смежных вершин, хранение весов не составляет проблемы: вес w(u,v) ребра (и, v) можно хранить в матрице на пересечении и-той строки и v-ro столбца. Для отсутствующих рёбер можно записать специальное значение NIL (в некоторых задачах вместо этого пишут 0 или оо). Для небольших графов, когда места в памяти достаточно, матрица смежности бывает удобнее - с ней часто проще работать. Кроме того, если не надо хранить веса, то элементы метрицы смежности представляют собой биты, и их можно размещать по нескольку в одном машинном слове, что даёт заметную экономию памяти. Упражнения 23.1-1 Граф хранится в виде списков смежности. Сколько операций нужно, чтобы найти число выходящих из данной вершины рёбер? число входящих в данную вершину рёбер? 23.1-2 Укажите представление в виде списков смежности и матрицу смежности для графа, являющегося полным двоичным деревом с 7 вершинами (пронумерованными от 1 до 7 как при сортировке с помощью кучи в главе 7). 23.1-3 Что произойдёт с матрицей смежности ориентированного графа, если обратить направления стрелок на всех его рёбрах, заменив каждое ребро (и, v) на ребро (v, и)? Как обратить напраления стрелок, если граф хранится в форме списков смежности? Оцените требуемое для этого число операций. 23.1-4 Мультиграф G = (V, Е) представлен в виде списков смежных вершин. Как за время 0(V + Е) преобразовать его в обычный неориентированный граф G = (V,E), заменив кратные рёбра на обычные и удалив рёбра-циклы? 23.1-5 Квадратом (square) ориентированного графа G = (V, Е) называется граф G2 = (V, Е2), построенный так: (и, w) £ Е2, если существует вершина v £ V, для которой (и, v) £ Е и (v,w) £ Е (две вершины соединяются ребром, если раньше был путь из двух рёбер). Как преобразовать G в G2, если граф хранится в виде списков смежных вершин? как матрица смежности? Оцените время работы ваших алгоритмов. 23.1-6 Почти любой алгоритм, использующий матрицы смежности, требует времени Q(V2) (просто на чтение этой матрицы), но бывают и исключения. Покажите, что за время 0(V) по матрице смежно- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||