Структуры данных и алгоритмы (1021739), страница 46
Текст из файла (страница 46)
Далее, определенные состояния назначаются допускающими состояниями. Для наших целей предположим, что только состояния, выражающиеся четными числами,являются допускающими. Два состояния называются эквивалентными, еслиявляются одним и тем же состоянием, или (1) они являются допускающимиили оба недопускающими; (2) вход 0 они преобразуют в эквивалентные состояния и (3) вход 1 они также преобразуют в эквивалентные состояния. Очевидно, что эквивалентные состояния "работают" одинаково на всех последовательностях входов, т.е.
на основании конкретных входов оба или достигнутмножества допускающих состояний, или не достигнут этого множества. Напишите программу, использующую операторы АТД MFSET, которая бы вычисляла множества эквивалентных состояний для данного конечного автомата.**5.21. Для реализации АТД MFSET посредством деревьев покажите, чтоа) если используется сжатие путей и разрешается сливать только большие деревья в меньшие, то для выполнения п операций слияния требуется времяпорядка Q(n logn);б) если используется сжатие путей, но всегда только меньшие деревья сливаются в большие, то для выполнения п операций слияния в самом худшемслучае требуется время порядка О(п сс(л)).5.22.
Выберите структуру данных и напишите программу вычисления множествPLACES (определены в разделе 5.6), которая выполнялась бы за среднее времяпорядка О(п) для строк длиной п.*5.23. Измените процедуру НОП из листинга 5.15 так, чтобы она действительно вычисляла НОП.*5.24. Напишите программу SPLIT для работы с 2-3 деревьями.*5.25.
Пусть элементы множества, представленного посредством 2-3 дерева, содержаттолько поле ключей, а элементы, которые хранятся во внутренних узлах, неимеют представительства в листьях. С учетом этих предположений перепишите операторы словарей, избегая хранения каких-либо элементов в двух различных узлах.Библиографические примечанияНагруженные деревья (trie) впервые предложены в работе [38]. В [6] введены Вдеревья (с которыми мы познакомимся в главе 11) как обобщения 2-3 деревьев.Впервые использовали деревья 2-3 для вставки и удаления элементов и для слиянияи разбиения множеств Дж.
Хопкрофт (J. E. Hopcroft) в 1970 г. (не опубликовано), адля оптимизации кодов — Дж. Ульман (J. D. Ullman) [111].Структуры деревьев из раздела 5.5, использующие сжатие путей и слияние меньших деревьев в большие, впервые применили М. Мак-Илрой (М. D. Mcllroy) и Р.Моррис (R. Morris) для построения остовных деревьев минимальной стоимости.
РеаУПРАЖНЕНИЯ181лизация АТД MFSET посредством деревьев проанализирована в работах [31] и [53].Упражнение 5.21,6 взято из статьи [108].Решение задачи НОП из раздела 5.6 приведено в [55]. Эффективная структура данных для операторов FIND, SPLIT и суженного оператора MERGE (когда все элементы водном множестве меньше по величине, чем в другом) приведена в статье [113].Упражнение 5.6 основано на эффективном алгоритме сравнения шаблонов, разработанном в [116]. Вариант 2-3 деревьев из упражнения 5.16 подробно рассмотрен в монографии [126]. Структура АВЛ-деревьев для упражнения 5.18 взята из работы [1].\182ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВГЛАВА 6ОриентированныеграфыВо многих задачах, встречающихся в компьютерных науках, математике, технических дисциплинах часто возникает необходимость наглядного представления отношений между какими-либо объектами.
Ориентированные и неориентированные графы — естественная модель для таких отношений. В этой главе рассмотрены основные структуры данных, которые применяются для представление ориентированныхграфов, а также описаны некоторые основные алгоритмы определения связностиориентированных графов и нахождения кратчайших путчей.6.1. Основные определенияОриентированный граф (или сокращенно орграф) G = (V, Е) состоит из множествавершин V и множества дуг Е. Вершины также называют узлами, а дуги — ориентированными ребрами. Дуга представима в виде упорядоченной пары вершин (v, w), гдевершина и называется началом, aw — концом дуги. Дугу (v, w) часто записываюткак v —> w и изображают в видеГоворят также, что дуга v —» w ведет от вершины v к вершине w, а вершина wсмежная с вершиной и.Пример 6.1.
На рис. 6.1 показан орграф с четырьмя вершинами и пятью дугами. DРис. 6.1.Ориентированный графВершины орграфа можно использовать для представления объектов, а дуги — дляотношений между объектами. Например, вершины орграфа могут представлять города, а дуги — маршруты рейсовых полетов самолетов из одного города в другой.
Вдругом примере, рассмотренном нами ранее в разделе 4.2, в виде орграфа представлена блок-схема потока данных в компьютерной программе. В последнем примеревершины соответствуют блокам операторов программы, а дугам — направленное перемещение потоков данных.Путем в орграфе называется последовательность вершин vi, V2, ..., vn, для которой существуют дуги v± -» v2, vz -> i>3, ..., un-i -> vn. Этот путь начинается в вершинеvi>! и, проходя через вершины и2» ^зn-\< заканчивается в вершине vn.
Длина пу-ти — количество дуг, составляющих путь, в данном случае длина пути равна л - 1.Как осрбый случай пути рассмотрим одну вершину и как путь длины О от вершины vк этой же вершине v. На рис. 6.1 последовательность вершин 1, 2, 4 образуют путьдлины 2 от вершины 1 к вершине 4.Путь называется простым, если все вершины на нем, за исключением, можетбыть, первой и последней, различны. Цикл — это простой путь длины не менее 1,который начинается и заканчивается в одной и той же вершине.
На рис. 6.1 вершины 3, 2, 4, 3 образуют цикл длины 3.Во многих приложениях удобно к вершинам и дугам орграфа присоединить какуюлибо информацию. Для этих целей используется помеченный орграф, т.е. орграф, у которого каждая дуга и/или каждая вершина имеет соответствующие метки. Меткой можетбыть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа.Пример 6.2. На рис. 6.2 показан помеченный орграф, в котором каждая дуга имеет буквенную метку.
Этот орграф имеет интересное свойство: любой цикл, начинающийся в вершине 1, порождает последовательность букв а и Ь, в которой всегда четное количество букв а и Ь. ОРис. 6.2. Помеченный орграфВ помеченном орграфе вершина может иметь как имя, так и метку. Часто меткивершин мы будем использовать в качестве имен вершин. Так, на рис. 6.2 числа, помещенные в вершины, можно интерпретировать как имена вершин и как метки вершин.6.2. Представления ориентированных графовДля представления ориентированных графов можно использовать различныеструктуры данных. Выбор структуры данных зависит от операторов, которые будутприменяться к вершинам и дугам орграфа. Одним из наиболее общих представленийорграфа G = (V, Е) является матрица смежности.
Предположим, что множествовершин V = {1, 2, ..., п). Матрица смежности для орграфа G — это матрица А размера п х п со значениями булевого типа, где A[i, j] = true тогда и только тогда, когдасуществует дуга из вершины i в вершину /'. Часто в матрицах смежности значениеtrue заменяется на 1, а значение false — на 0. Время доступа к элементам матрицысмежности зависит от размеров множества вершин и множества дуг. Представлениеорграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которыхнадо часто проверять существование данной дуги.Обобщением описанного представления орграфа с помощью матрицы смежностиможно считать представление помеченного орграфа также посредством матрицысмежности, но у которой элемент A[i, j] равен метке дуги i —> /.
Бели дуги от вершины i к вершине /' не существует, то значение A(i, j] не может быть значением какойлибо допустимой метки, а может рассматриваться как "пустая" ячейка.Пример 6.3. На рис. 6.3 показана матрица смежности для помеченного орграфа изрис. 6.2. Здесь дуги представлены меткой символьного типа, а пробел используетсяпри отсутствии дуг. П184ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫОсновной недостаток матриц смежности заключается в том, что она требуетобъема памяти, даже если дуг значительно меньше, чем п2. Поэтому для чтения матрицы или нахождения в ней необходимого элемента требуется время порядка О(п2),что не позволяет создавать алгоритмы с временем О(п) для работы с орграфами,имеющими порядка О(п) дуг.1234ааЪЪЪаЬаРис.
6.3. Матрица смежности для помеченного орграфаиз рис. 6.2Поэтому вместо матриц смежности часто используется другое представление дляорграфа G = (V, Е), называемое представлением посредством списков смежности.Списком смежности для вершины i называется список всех вершин, смежных с вершиной i, причем определенным образом упорядоченный. Таким образом, орграф Gможно представить посредством массива HEAD (Заголовок), чей элемент HEAD[i]является указателем на список смежности вершины i.
Представление орграфа с помощью списков смежности требует для хранения объем памяти, пропорциональныйсумме количества вершин и количества дуг. Бели количество дуг имеет порядокО(п), то и общий объем необходимой памяти имеет такой же порядок. Но и для списков смежности время поиска определенной дуги может иметь порядок О(п), так кактакой же порядок может иметь количество дуг у определенной вершины.Пример 6.4. На рис. 6.4 показана структура данных, представляющая орграф изрис.
6.1 посредством связанных списков смежности. Если дуги имеют метки, то ихможно хранить в ячейках связанных списков.• |i-»» *т | i •0Л».2•QHEADСписки смежностиРис. 6.4. Структура списков смежности для орграфа из рис. 6.1Для вставки и удаления элементов в списках смежности необходимо иметьмассив HEAD, содержащий указатель на ячейки заголовков списков смежности,но не сами смежные вершины1. Но если известно, что граф не будет подвергатьсяизменениям (или они будут незначительны), то предпочтительно сделать массивHEAD массивом курсоров на массив ADJ (от adjacency — смежность), где ячейкиADJ[HEAD[i}], ADJ[HEAD[i] + 1] и т.д. содержат вершины, смежные с вершинойi, и эта последовательность смежных вершин заканчивается первым встреченнымнулем в массиве ADJ.
Пример такого представления для графа из рис. 6.1 показан на рис. 6.5. D1Здесь проявляется старая проблема языка Pascal: сложность выполнения вставки и удаления произвольных позиций в простых связанных списках.6.2. ПРЕДСТАВЛЕНИЯ ОРИЕНТИРОВАННЫХ ГРАФОВ185ADJРис. 6.5. Другоепредставлениесписков смежности для графа изрис. 6.1АТД для ориентированных графовПо привычной схеме сначала надо формально определить абстрактные типы данных, соответствующие ориентированным графам, а затем рассмотреть операторы,выполняемые над этими АТД. Но мы не будем неукоснительно следовать этой схеме,так как на этом пути нам не встретятся большие неожиданности, а принципиальныеструктуры данных, используемые для представления орграфов, уже были описаныранее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
