Абстрактным принято называть тип данных, в явном виде не имеющийся в языке программирования, в этом смысле это понятие относительное - тип данных, отсутствующий в одном языке программирования, может присутствовать в другом.
Абстрактный тип данных (АТД) определяется независимо от способа его реализации:
множеством возможных значений этого типа,
и набором операций со значениями этого типа.
Использование АТД может быть ограничено этапом разработки программного обеспечения, но для его явного использования в программе надо иметь его реализацию на основе уже имеющихся (и ранее реализованных) типов данных в языке программирования:
способ представления значений этого типа,
и реализацию операций со значениями этого типа.
АТД не является предопределенным в языке программирования, и даже более того – операции конструирования таких типов, предопределенные в языке, перекладывают на разработчика-программиста вопрос о способе представления значений такого типа и реализации операций со значениями этого типа. А потому, для таких типов данных вопрос о выборе определений и способов реализации операций вида конструктор (значений и хранилищ данных) такого типа, селектор и модификатор компонентов (значений и хранилищ данных) такого типа возлагается на разработчика-программиста.
В концепции АТД особый статус имеют понятия интерфейс , открытый пользователю, и реализация , скрытая от него. Особая роль этих понятий в концепции АТД связана с основополагающим положением о независимости понятия АТД от способа его реализации.
В современных «практических языках программирования» для конструирования АТД обычно используется предопределенная операция конструирования типов class , которая дает разработчику-программисту не только средства группировки данных и операций (с этими данными) в единое целое, но и средства инкапсуляции, наследования и полиморфизма для управления способами конструирования и доступа к таким данным. Отметим, что класс описывает одну возможную реализацию АТД, отображение класса в АТД выражается функцией абстракции, но обратное отношение, обычно, не является функциональным, реализаций одного и того же АТД может быть несколько.
В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template , generic) .
Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:
Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).
Предикаты – отношения на элементах носителя. Это позволяет определять область возможных значений наложением ограничений (требований) на допустимые значения, а также в естественной трактовке работать с произвольными логическими выражениями, не принуждая интерпретировать их как функции принадлежности для множеств или как многозначные операции.
На такой основе можно рассматривать абстрактные типы данных с единой целостной логико-алгебраической точки зрения, включая вопросы о конструкторах (типов и значений), селекторах и модификаторах свойств для объектов такого типа .
Понятия «структура данных» и «абстрактный тип данных» в чем-то очень близкие. Можно конечно считать, что эти понятия - просто два взгляда на одно и то же. Способ представления значений АТД всегда основан на некоторой структуре данных, менее или более сложной, и реализация операций с такими значениями естественно зависит от этой выбранной структуры данных. С другой стороны, заинтересовавшую нас структуру данных при большом желании мы всегда можем оформить как АТД.
Но все же мы будем различать эти два понятия, учитывая:
Абстрактный тип данных - подразумевает определенный уровень абстрагирования с целью фиксации прикладного (предметно-ориентированного) типа данных безотносительно к способам его реализации, и возможно включения этого типа данных в прикладную библиотеку, ну хотя бы для конкретной разработки конкретной программной системы. АТД может иметь несколько альтернативных реализаций, основанных на различных структурах данных.
Структура данных - скорее некоторая схема организации данных и управления ими, которая предполагает соответствующие конкретизации при ее использовании в конкретных ситуациях при решении конкретных задач.
К абстрактным типам данных прежде всего естественно относятся математические базовые алгебраические системы – последовательности, множества, отношения и отображения (функциональные отношения, функции) . Но в программировании на переднем плане не исследование общих свойств этих математических понятий, а возможности их использования в разработке моделей решения задач предметной области, алгоритмов решения этих задач и эффективной реализации разработанных алгоритмов. А потому в программировании в виде АТД обычно оформляются с одной стороны ограниченные варианты этих базовых алгебраических систем, а с другой стороны расширенные специализированными наборами операций, представляющими прагматический интерес с точки зрения области применения.
Тип данных описывает множество объектов со схожими свойствами. Все традиционные языки программирования используют набор базовых типов данных (real, integer, string, character). Базовые типы данных подчиняются предопределенному набору операций. Например, базовый тип данных integer позволяет выполнять такие операции, как сложение, вычитание, умножение, деление.
В традиционные языки программирования включаются конструкторы типов, самым распространенным из которых является конструктор record. Например, для записи типа CUSTOMER можно определить поля данных. Запись CUSTOMER будет представлять собой новый тип данных, в котором будет храниться информация о клиенте, можно напрямую получать доступ к этой структуре данных, ссылаясь на имена полей. Над записью можно выполнять такие операции, как WRITE, READ, DELETE, UPDATE. Для базовых типов данных определить новые операции нельзя.
Как и базовые типы данных, абстрактные типы данных (ATD, abstract data types) описывают множество схожих объектов. Есть отличия ATD от традиционного типа данных:
· операции под ATD определяются пользователем;
· ATD не допускают непосредственного доступа к внутреннему представлению данных и реализации методов.
В некоторых ОО-системах (например, Smalltalk) базовые типы данных реализованы как абстрактные.
Для создания абстрактного типа данных необходимо обеспечить:
· имя типа;
· представление данных или переменные экземпляра объекта, принадлежащего ATD; каждая переменная экземпляра имеет тип данных, который может быть либо базовым типом, либо другим ATD;
· операции под ATD и ограничения реализуются с помощью методов.
Определение ATD перестраивает определение класса. В некоторых ОО-системах для различения классов и типов при ссылки на структуры данных и методы класса используется ключевое слово type, а при ссылке на набор экземпляров объекта - ключевой слово class. Тип (type) более статичное понятие, а class связан в основном со временем выполнения. Отличие ОО-класса от ОО-типа можно проиллюстрировать на примере. Предположим, имеется шаблон для конструктора. К шаблону прилагается описание его структуры, а также инструкция по его использованию. Этот шаблон и есть описание типа (type definition). Комплект сделанных с помощью шаблона реальных изделий, каждое из которых имеет уникальный номер (или OID), составляет класс (class).
ATD совместно с наследованием позволяют создавать сложные объекты. Сложный объект (complex object) формируется путем комбинации других объектов, находящихся в сложных взаимосвязях друг с другом. Пример сложного объекта можно найти в системах безопасности, где используются различные типы данных:
1. стандартные (табличные) данные о сотруднике (ФИО, Таб. № и т.д.);
2. битовая карта для хранения фотографии сотрудника;
Возможность относительно просто работать с такой сложной средой данных повышает значение ОО-систем на современном рынке баз данных.
Абстрактный тип данных
Абстра́ктный тип да́нных (АТД) - это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций , а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения - в этом и заключается суть абстракции . Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями. Конкретные реализации АТД называются структурами данных .
В программировании абстрактные типы данных обычно представляются в виде интерфейсов , которые скрывают соответствующие реализации типов. Программисты работают с абстрактными типами данных исключительно через их интерфейсы, поскольку реализация может в будущем измениться. Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании . Сильной стороной этой методики является именно сокрытие реализации. Раз вовне опубликован только интерфейс, то пока структура данных поддерживает этот интерфейс, все программы, работающие с заданной структурой абстрактным типом данных, будут продолжать работать. Разработчики структур данных стараются, не меняя внешнего интерфейса и семантики функций, постепенно дорабатывать реализации, улучшая алгоритмы по скорости, надежности и используемой памяти.
Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных методов динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций.
Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
Примеры АТД
См. также
Ссылки
- Лапшин В. А. Абстрактные типы данных в программировании
Wikimedia Foundation . 2010 .
Смотреть что такое "Абстрактный тип данных" в других словарях:
абстрактный тип данных - Тип данных (абстрактный класс), определенный посредством перечисления его методов и свойств, без создания их конкретной реализации. Тематики информационные технологии в целом EN Abstract Data TypeADT … Справочник технического переводчика
В теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия
Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия
У этого термина существуют и другие значения, см. Множество (значения). Множество тип и структура данных в информатике, является реализацией математического объекта множество. Данные типа множество позволяют хранить ограниченное число значений… … Википедия
Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия
У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия
Один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия
Типаж (англ. trait) это абстрактный тип, в информатике, используемый, как «простая концептуальная модель для структурирования объектно ориентированных программ». Типажи подобны mixins, но могут включать определения методов класса.… … Википедия
Бинарное дерево, простой пример ветвящейся связной структуры данных. Структура данных (англ. data structure) программная единица, позволяющая хран … Википедия
- (top type) в теории типов, часто обозначаемый как просто вершина или «закрепленным» символом (⊤), универсальный тип, то есть такой тип, который содержит в себе каждый возможный объект в нужной системе типов. Высший тип иногда именуется… … Википедия
Доброго времени суток, хабравчане!
Следующий пост является изложением моих размышлений на тему природы классов и АТД. Эти размышления дополнены интересными цитатами из книг гуру разработки программного обеспечения
Введение
Начнем с того, что плавно подойдем к определению АТД. АТД, в первую очередь, представляет собой тип данных, что означет следущее:наличие определенных доступных операций над элементами этого типа;
а также данные, относительно которых эти операции выполняются (диапазон значений).
Что же означает слово “абстрактный”? В первую очередь понятие “абстрактность” означет сосредоточение внимания на чем-то важном и, при этом, нам нужно отвлечься от неважных, на данный момент, деталей. Определение абстрактности хорошо раскрыто в книге Гради Буча (“Grady Booch”). Звучит определение так:
Абстракция – это выделение и придание совокупности объектов общих свойств, которые определяют их концепутальные границы и отличают от всех других видов объектов.
Иными словами, абстракция позволяет “пролить свет” на нужные нам данные объектов и, при этом, “затенить” те данные, которые нам не важны.
Итак, что же будет, если слить понятия “тип данных” и “абстракция” воедино? Мы получим тип данных, который предоставляет нам некий набор операций, обеспечивающих поведение объектов этого типа данных, а также этот тип данных будет скрывать те данные, с помощью которых реализовано данное поведение. Отсюда, приходим к понятию АТД:
АТД – это такой тип данных, который скрывает свою внутреннюю реализацию от клиентов.
Удивительно то, что путем применения абстракции АТД позволяет нам не задумываться над низкоуровневыми деталями реализации, а работать с высокоуровневой сущностью реального мира (Стив Макконнелл).
Я считаю, что при разработке АТД сначала нужно определить интерфейс, так как интерфейс не должен зависеть от внутреннего представления данных в АТД. После определения операций, сотставляющих интерфейс, нужно сосредоточиться на данных, которые и будут реализовать заданное поведение АТД. В итоге мы получим некую структуру данных – механизм позволяющий хранить и обрабатывать данные. При этом, прелесть АТД в том, что если нам захочется изменить внутренне представление данных, то нам не придется блуждать по всей программе и менять каждую строку кода, которая зависит от данных, которые мы хотим поменять. АТД инкапсулирует эти данные, что позволяет менять работу объектов этого типа, а не всей программы.
Преимущества АТД
Использование АТД имеет массу преимуществ (все описанные преимущества можно найти в книге Стива Макконнелла «Совершенный код”):
- Инкапсуляция деталей реализации.
Это означает, что единожды инкапсулировав детали реализации работы АТД мы предоставляем клиенту интерфейс, при помощи которого он может взаимодействовать с АТД. Изменив детали реализации, представление клиентов о работе АТД не изменится.
- Снижение сложности.
Путем абстрагирования от деталей реализации, мы сосредатачиваемся на интерфейсе, т.е на том, что может делать АТД, а не на том как это делается. Более того, АТД позволяет нам работать с сущностью реального мира.
- Ограничение области использования данных.
Используя АТД мы можем быть уверены, что данные, представляющие внутреннюю структуру АТД не будут зависеть от других участков кода. При этом реализуется “независимость” АТД.
- Высокая информативность интерфейса.
АТД позволяет представить весь интерфес в терминах сущностей предметной области, что, согласитесь, повышает удобочитаемость и информативность интерфейса.
Стив Макконнелл рекомендует представлять в виде АТД низкоуровнеые типы данных, такие как стек или список. Спросите себя, что представляет собой этот список. Если он представляет список сотрудников банка, то и рассматривайте АТД как список сотрудников банка.
Итак, мы разобрались, что такое АТД и назвали преимущества его применения. Теперь стоит отметить, что при разработке классов в ООП следует думать, в первую очередь, об АТД. При этом, как сказал Стив МакКоннелл, Вы программируете не на языке, а с помощью языка. Т.е Вы будете программировать выходя за рамки языка, не ограничиваясь мыслями в терминах массивов или простых типов данных. Вместо этого Вы будете думать на высоком уровне абстракции (например, в терминах электронных таблицах или списков сотрудников). Класс – это не что иное как дополнение и способ реализации концепции АТД. Мы можем даже представить класс в виде формулы:
Класс = АТД + Наследование + Полиморфизм.
Так почему же следут думать об АТД, при разработке классов. Потому что, сперва мы должны решить какие операции будут составлять интерфейс будущего класса, какие данные скрыть, а к каким предоставить открытый доступ. Мы должны подумать об обеспечении высокой информативности интерфейса, легкости оптимизации и проверки кода, а также о том, как бы нам предоставить правильную абстракцию, чтобы можно было думать о сущностях реального мира, а не о низкоуровнеых деталях реализации. Я считаю, что именно после определения АТД мы должны думать о вопросах наследования и полиморфизма.
Стоит отметить, что концепция АТД нашла гирокое применение в ООП, т.к именно эта концепция дополняет ООП и позволяет уменшить сложность программ в быстроменяющемся мире требований к ПО.
Данную статью я писал для того, что бы обратить внимание разработчиков на АТД с целью повышения качества работы и разработки программного обеспечения.
Использованные источники:
Стив Макконнелл – “Совершенный код”;
Роберт Седжвик – «Алгоритмы на Java».
Приложение к рабочей программе по дисциплине «Структуры и алгоритмы обработки данных в ЭВМ»
Абстрактный тип данных "Список".
Список – последовательность элементов определенного типа a 1 , a 2 , ..., a n , где n https://pandia.ru/text/78/308/images/image001_307.gif" width="13" height="16">1, то a 1
Называется первым элементом, а an – последним элементом списка. Элементы списка линейно упорядочены в соответствии с их позицией в списке. Элемент ai предшествует элементу ai +1 для i = 1,2, n -1 и ai следует за ai -1 для i = 2,3, n . Каждый элемент списка ai имеет позицию i , i =1,2, n . В списке существует позиция, означающая конец списка – nil . Она следует за последним элементом списка.
Операторы АТД "Список":
1. INSERT(x , р, L ). Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Таким образом, если список L состоит из элементов a 1 , a 2 , ..., а n а1, а2, ..., ар-1, х, ар, ..., a n. . Если р принимает значение nil , то будем иметь a 1 , a 2 , ..., a n , , х . Если в списке L нет позиции р, то результат выполнения этого оператора не определен.
2. LOCATE (x , L ). Эта функция возвращает позицию объекта х в списке L. Если в списке объект x встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L , то возвращается nil .
3. RETRIEVE (p , L ). Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определен, если р = nil или в списке L нет позиции р.
4. DELETE (p , L ). Этот оператор удаляет элемент в позиции р списка L. Так, если список L состоит из элементов a 1 , a 2 , ..., а n , то после выполнения этого оператора он будет иметь вид а1, а2, ...,, ap - i , ap + i , ..., а n. Результат не определен, если в списке L нет позиции р или р = nil .
5. NEXT(p, L ) и PREVIOUS(p, L ). Эти функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р - последняя позиция в списке L, то NEXT(p , L ) = nil . Функция NEXT не определена, когда р= nil . Функция PREVIOUS не определена, если р = 1. Обе функции не определены, если в списке L нет позиции р.
6. MAKENULL ( L ) . Эта функция делает список L пустым и возвращает позицию nil .
7. FIRST (L ). Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция nil .
8. PRINTLIST (L ). Печатает элементы списка L в порядке их расположения в списке.
Представление списка с помощью массива:
Представление списка с помощью односвязного списка:
Обозначения:
· – указатель на начало списка,
· last - указатель на последний элемент в списке,
· maxlenght – максимальная длина (количество элементов) в списке.
Представление списка с помощью двусвязного списка:
Упражнения:
1. Напишите программы вставки, удаления и поиска элементов отсортированного списка, используя для реализации списка
§ массив,
§ указатели.
2. Напишите программу для слияния
§ двух отсортированных связных списков,
§ n отсортированных связных списков,
3. Дан многочлен вида
р(х) = с1 х e 1 + c 2 xe 2 + + с n х n , где е1 > е2 > ... > e n > 0.
Такой многочлен можно представить в виде связанного списка, где каждый элемент имеет три поля: одно - для коэффициента с i второе - для показателя степени е i третье - для указателя на следующий элемент. Для описанного, представления многочленов напишите программу сложения и умножения многочленов, используя это представление.
4. Реализуйте АТД LIST (Список) для любого типа данных и его операторы INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST:
§ список задан в виде массива,
§ список задан в виде односвязного списка,
§ список задан в виде двусвязного списка.
Раздел рабочей программы 2.1.2
Абстрактный тип данных "Стек".
Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной , (top). Для стека используется метод доступа LIFO (last-in-first-out - последний вошел - первый вышел).
Операторы АТД "Стек":
1. MAKENULL (S ). Делает стек S пустым.
2. TOP (S ). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).
3. POP (S ). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S ).
4. PUSH (x , S ). Вставляет элемент х в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т. д. В терминах общих операторов списка данный оператор можно записать как INSERT(;c, FIRST(S), S ).
5. EMPTY (S ) . Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.
массива:
Представление стека с помощью односвязного списка:
Упражнения:
Реализуйте АТД STACK(Стек) для любого типа данных и его операторы MAKENULL, TOP, POP, PUSH, EMPTY.
§ стек задан в виде массива,
§ стек задан в виде односвязного списка.
Раздел рабочей программы 2.1.2
Абстрактный тип данных "Очередь".
Очередь (queue) - это специальный тип списка, где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют "списками типа FIFO" (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел - первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка , а не в начало, как в стеках.
Операторы АТД "Очередь":
1. MAKENULL (Q ) очищает очередь Q, делая ее пустой.
2. FRONT (Q ) - функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).
3. ENQUEUE (a , Q ) вставляет элемент х в конец очереди Q.
С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, END(Q), Q).
4. DEQUEUE (Q ) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q), Q).
5. EMPTY (Q ) возвращает значение true тогда и только тогда, когда Q является пустой очередью.
циклического массива:
Обозначения:
Q – очередь,
Q . front – указатель на начало очереди,
Q . rear - укаазатель на конец очереди.
Представление очереди с помощью односвязного списка:
Упражнения:
Реализуйте АТД QUEUE (Очередь) для любого типа данных и его операторы MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY.
§ очередь задана в виде циклического массива,
§ очередь задана в виде двусвязного списка.
Абстрактный тип данных "Дерево".
Дерево - это совокупность элементов, называемых узлами (один из которых определен как корень ), и отношений ("родительских"), образующих иерархическую структуру узлов. Узлы, так же, как и элементы списков, могут быть элементами любого типа. Формально дерево можно рекуррентно определить следующим образом.
1. Один узел является деревом. Этот же узел также является корнем этого дерева.
2. Пусть п - это узел, a T 1 , Т2, ..., Tk - деревья с корнями n 1 . n 2 , ..., nk соответственно. Можно построить новое дерево, сделав п родителем узлов n 1 . n 2 , ..., nk . В этом дереве п будет корнем, a T 1 , Т2, ..., Tk - поддеревьями этого корня. Узлы n 1 . n 2 , ..., nk называются сыновьями узла п.
Часто в это определение включают понятие нулевого дерева , т. е. "дерева" без узлов, такое дерево обозначается словом nill .
Пример: О главление книги, схематически можно представить деревом. Отношение родитель-сын отображается в виде линии. Деревья обычно рисуются сверху вниз так, что родители располагаются выше "детей".
DIV_ADBLOCK135">
Высотой узла дерева называется длина самого длинного пути из этого узла до какого-либо листа. В примере высота узла Гл.1 равна 1, узла Гл.2 - 2, а узла Гл. З - 0. Высота дерева совпадает с высотой корня. Глубина узла определяется как длина пути (он единственный) от корня до этого узла.
Сыновья узла обычно упорядочиваются слева направо. Поэтому два дерева на рисунке различны, так как порядок сыновей узла а различен. Если порядок сыновей игнорируется, то такое дерево называется неупорядоченным , в противном случае дерево называется упорядоченным .
Операторы АТД "Дерево":
1. PARENT (n , Т). Эта функция возвращает родителя (parent) узла п в дереве Т. Если п является корнем, который не имеет родителя, то в этом случае возвращается nill . Здесь nill указывает на то, что произошел выход за пределы дерева.
2. LEFTMOST __ CHILD (n , Т). Данная функция возвращает самого левого сына узла n в дереве Т. Если n является листом (и поэтому не имеет сына), то возвращается nill .
3. RIGHT _ SIBLING (n , Т). Эта функция возвращает правого брата узла п в дереве Т или значение nill , .если такового не существует. Для этого находится родитель р узла п и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от. узла п.
4. LABEL (n , T ). Возвращает метку узла n . дерева Т. Для выполнения этой функции требуется, чтобы на узлах дерева были определены метки.
5. CREATE (v , T 1 , T 2 , ..., Ti ,) - это cемейство функций, которые для каждого i = 0, 1, 2,... создают новый корень r с меткой v и далее для этого корня создает i сыновей, которые становятся корнями поддеревьев T 1 , Т2, .... Ti ;. Эти функции возвращают дерево с корнем r . Отметим, что если i = 0, то возвращается один узел r , который одновременно является и корнем, и листом.
6. ROOT (T ) возвращает узел, являющимся корнем дерева T , Если T - пустое дерево, то возвращается nill .
7. MAKENULL (T ). Этот оператор делает дерево T пустым деревом.
Представление дерева с помощью массива родителей:
Представление дерева с помощью связанных списков:
Представление дерева посредством, левых сыновей и правых братьев.
Обозначения в рисунке:
nodespace – массив узлов дерева,
- label
–
метка узла,
header
–
индекс левого сына в списке сыновей,
cellspase – массив списков сыновей узлов,
- node
–
указатель на узел в массиве
nodespace
,
next
–
индекс правого сына в списке сыновей.
Упражнения:
1. Дано дерево:
DIV_ADBLOCK137">
§ дерево задано в виде массива записей узлов, содержащих индекс самого левого сына, индекс правого брата и метку,
§ связное двоичное дерево задано с помощью указателей на левого и правого сыновей.
4. Напишите функции обхода двоичного дерева в прямом, обратном и симметричном порядке.
Раздел рабочей программы 2.1.3
Абстрактный тип данных "Множество".
Множество обычно изображается в виде последовательности его элементов, заключенной в фигурные скобки, например {1, 4} обозначает множество, состоящее из двух элементов, - чисел 1 и 4. Порядок, в котором записаны элементы множества, не существен, поэтому можно писать {4, 1} так же, как и {1, 4}, при записи одного и того же множества. Множество не является списком (хотя бы по признаку произвольного порядка записи элементов). В множестве отсутствуют повторяющиеся элементы ({1, 4, 1} не является множеством).
Фундаментальным понятием теории множеств является понятие отношения принадлежности к множеству , обозначаемое символом . Таким образом, запись х х не принадлежит множеству А ", т. е. х не является элементом множества А . Существует специальное множество, обозначаемое символом , которое называется пустым, множеством , и которое не имеет элементов. Множество DIV_ADBLOCK138">
Говорят, что множество А содержится в множестве В (или включается в множество В), пишется A В или В А , если любой элемент множества А является также элементом множества В. В случае A В также говорят, что множество А является подмножеством множества В.
Например, {1, 2} https://pandia.ru/text/78/308/images/image019_36.gif" width="15" height="15 src=">В и А В, то множество А называют собственным, истинным или строгим подмножеством множества В.
Основными операциями, выполняемыми над множествами, являются операции объединения, пересечения и разности. Объединением множеств А и В (обозначается А В) называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств A и В.
Пересечением множеств А и В (обозначается А В) называется множество, состоящее только из тех элементов, которые принадлежат и множеству А , и множеству В. Разностью множеств А и В (обозначается A \ B ) называется множество, состоящее только из тех элементов множества А , которые не принадлежат множеству В .
Например, если А = {а, b, с} и В= {b, а}, то А В= {а, b, с, d}, A В = { b } и А \ В = {а, с}.
Операторы АТД “Множество”:
1. UNION (A , В, С) А и В С, равное А В.
2. INTERSECTION (A , В, С) имеет "входными" аргументами множества А и В , а в качестве результата - "выходное" множество С, равное А В. .
3. DIFFERENCE (A , В, С) имеет "входными" аргументами множества А и В , а в качестве результата - "выходное" множество С, равное А\ В.
4. MERGE ( A , В, С) оператор выполняет слияние (merge ), или объединение непересекающихся множеств . Этот оператор не отличается от оператора. UNION , но здесь предполагается, что множества-операнды не пересекаются (т. е. не имеют общих элементов). Оператор присваивает множеству С значение А В , но результат будет не определен, если А В , т. е. в случае, когда множества А и В имеют общие элементы.
5. member (х, А ) имеет аргументами множество А и объект х того же типа, что и элементы множества А , и возвращает булево значение true (истина), еcли х a", "b", "с"})= "а". Подобным образом определяется оператор МАХ .
11.EQUAL (A , В ) возвращает значение true тогда и только тогда, когда множества А и В состоят из одних и тех же элементов.
12. FIND (x ) оперирует в среде, где есть набор непересекающихся множеств. Он возвращает имя (единственное) множества, в котором есть элемент х.
Представление множества:
Множество можно задать с помощью массива или связного списка.
Упражнения:
1. Заданы два множества А = {1, 2, 3} и В = {3, 4, 5}. Каков будет результат выполнения следующих операторов?
· UNION(A. В. С),
· INTERSECTION(A, В, С),
· DIFFERENCE(A. В. С),
· MEMBER(l. A),
· INSERT(1,А),
· DELETE(1, А),
2. Реализуйте АТД “Множество” для любого типа данных и его операторы MAKENULL, UNION, INTERSECTION, MEMBER, MIN.
· множество задано с помощью массива фиксированной длины и указателя на последнюю занятую позицию в массиве,
· множество задано с помощью несортированного связного списка,
· множество задано с помощью отсортированного связного списка,
Раздел рабочей программы 2.1.3
Специальные виды множеств
Абстрактный тип данных “Дерево двоичного поиска”
Дерево двоичного поиска - структура данных для представления множеств, чьи элементы упорядочены посредством некоторого отношения линейного порядка. На деревьях двоичного поиска можно реализовать операторы множества INSERT , DELETE , MEMBER и MIN , причем время их выполнения в среднем имеет порядок O (log n) для множеств, состоящих из п элементов.
Характерным для дерева двоичного поиска является то, что его узлы помечены элементами множеств (узлы дерева содержат элементы множества). Причем, все элементы, хранящиеся в узлах левого поддерева любого узла х, меньше элемента, содержащегося в узле х, а все элементы, хранящиеся в узлах правого поддерева узла х, больше элемента, содержащегося в узле х.
Примеры двоичного дерева:
https://pandia.ru/text/78/308/images/image023_7.jpg" width="277" height="122 src=">
Представление АВЛ-дерева не отличается от представления двоичного дерева поиска.
Другой разновидностью сбалансированного дерева поиска является 2-3 дерево. Структура 2-3 дерева отличается от структуры дерева двоичного поиска.Для 2-3 дерева характерно, что все узлы имеют 2 или 3 сына, все пути от корня до листа имеют одинаковую длину и все элементы множества содержатся в листьях. Узлы 2-3 дерева делятся на внутренние и терминальные (листья). Внутренние узлы используются только для маршрутизации поиска в дереве. Каждый внутренний узел содержит ключи наименьших элементов второго и третьего сына (если есть третий сын)и указатели на узлы сыновей.
Представление связного дерева двоичного поиска:
Представление сбалансированного связного 2-3 дерева:
Упражнения:
1. Нарисуйте все возможные деревья двоичного поиска для четырех элементов 1, 2, 3 и 4.
2. Вставьте целые числа 7, 2, 9, 0, 5, 6, 8, 1 в пустое дерево двоичного поиска.
3. Покажите результат удаления числа 7, а затем числа 2 из дерева, полученного в предыдущем упражнении.
4. Нарисуйте 2-3 дерево, которое получится в результате вставки в пустое множество (представленное как 2-3 дерево) элементов 5, 2, 7, 0, 3, 4, 6, 1, 8, 9.
5. Покажите результат удаления элемента 3 из 2-3 дерева, полученного в предыдущем упражнении.
3. Реализуйте АТД “Дерево поиска” для любого типа данных и его операторы INSERT, DELETE, MEMBER и MIN.
· дерево задано в виде связного двоичного дерева
· дерево задано в виде 2-3 дерева
Раздел рабочей программы 2.1.3
Абстрактный тип данных "Словарь".
Словарь – множество, предназначенное для хранения "текущих" объектов с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве. Словарь реализуется с помощью АТД “Словарь” с операторами INSERT, DELETE и MEMBER . В набор операторов словаря также входит оператор MAKENULL для инициализации структур данных АТД.
Словарь можно представить с помощью хеш-таблицы. Таблица строится на основе следующей идеи: потенциальное множество элементов (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от 0 до В -1 , строится хеш-функция h такая, что для любого элемента х исходного множества функция h(x} принимает целочисленное значение из интервала 0, ..., В - 1, которое, соответствует классу, которому принадлежит элемент х. Элемент х часто называют ключом, h( x) - хеш -значением х, а "классы" – сегментами . Поспособу разрешения коллизий хеширования (два элемента множества имеют одинаковое значение h(x) ) применяется открытое и закрытое хеширование.
открытой хеш-таблицы
Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0, 1,...,В - 1 , содержит заголовки для В связных списков. Элемент i -го списка - это элемент исходного множества, для которого h (.х:) = i .
Представление словаря с помощью закрытой хеш-таблицы
В таблице сегментов хранятся непосредственно элементы словаря. Поэтому в каждом сегменте можно хранить только один элемент словаря. При закрытом хешировании применяется методика повторного хеширования . При попытке поместить элемент x в сегмент с номером h ( x ) , который уже занят другим элементом выбирается последовательность номеров сегментов h 1 ( x ) ,h 2 ( x ) , … , куда можно поместить элемент. Последовательно проверяется занятость каждого из этих сегментов, пока не будет найден свободный сегмент. В него помещается элемент x . Для задания номеров сегментов при повторном хешировании применяются различные методы разрешения коллизий. Например, метод линейного хеширования, метод середины квадрата, метод случайного хеширования
Упражнения:
1. Предположим, что для хеширования целых чисел в 7-сегментную хеш-таблицу используется хеш-функция h(i) = i % 7.
· приведите результирующую хеш-таблицу, если в нее вставляются точные кубы 1, 8, 27,64,125, 216,343;
· повторите предыдущий пункт для закрытой хеш-таблицы с линейной методикой разрешения коллизий.
2. Предположим, что есть закрытая хеш-таблица с 5 сегментами, хеш-функцией h(i) = i % 5 и линейной методикой разрешения коллизий. Покажите результат вставки в первоначально пустую хеш-таблицу последовательности чисел 23, 48, 35, 4, 10.
3. Реализуйте АТД “Словарь” для текстовых строк и его операторы INSERT, DELETE, MEMBER и MAKENULL
· словарь задан с помощью открытой хеш-таблицы,
· словарь задан с помощью закрытой хеш-таблицы с линейной методикой разрешения коллизий,
Раздел рабочей программы 2.1.3
Абстрактный тип данных " Отображение".
Отображение - это множество, на элементах которого определена функция отображения элементов одного типа (области определения ) на элементы другого типа (области значений ) другого типа. Отображение М ставит в соответствие элемент d типа domaintype из области определения элементу r типа rangetype из области значений: M (d ) = r .Пустое отображение не содержит никаких элементов
Операторы АТД "Отображение":
1. MAKENULL (M ). Делает отображение М пустым.
2. ASSIGN(М d, r). Делает M (d ) равным r независимо от того, как M (d ) было определено ранее.
3. COMPUTE(M, d, r). Возвращает значение true и присваивает переменной r значение M (d ), если последнее определено, и возвращает false в противном случае.
Представление отображения: отображение можно эффективно реализовать с помощью хеш-таблиц. Здесь x задает значение из области определения отображения, а элемент таблицы с номером h ( x ) – элемент из области значений.
Раздел рабочей программы 2.1.3
Абстрактный тип данных “Очередь с приоритетами”
Очередь с приоритетами - это множество, для элементов которого задана функция приоритета (priority), т. е. для каждого элемента x множества можно вычислить функцию р( x )- приоритет элемента x , которая обычно принимает значения из множества действительных чисел, или, в более общем случае, из некоторого линейно упорядоченного множества.
АТД “Очередь с приоритетом” основано на АТД “Множество” с операторами INSERT и DELETEMIN , а также с оператором MAKENULL для инициализации структуры данных. Оператор INSERT для очереди с приоритетами понимается в обычном смысле, тогда как DELETEMIN является функцией, которая возвращает элемент с наименьшим приоритетом и в качестве побочного эффекта удаляет его из множества.
Представление очереди с помощью упорядоченного двузвязного списка.
Представление очереди с помощью частично упорядоченного связного дерева:
Основная идея такой реализации заключается в том, чтобы организовать элементы очереди в виде двоичного дерева. На нижнем уровне, где некоторые листья могут отсутствовать, все отсутствующие листья могут располагаться только справа от присутствующих листьев нижнего уровня. Более существенно, что дерево частично упорядочено . Это означает, что приоритет узла v не больше приоритета любого сына узла v , где приоритет узла - это значение приоритета элемента, хранящегося в данном узле. Из рисунке видно, что малые значения приоритетов не могут появиться на более высоком уровне, где есть большие значения приоритетов.
При выполнении функции DELETEMIN возвращается элемент с минимальным приоритетом, который должен быть корнем дерева. Чтобы не разрушить дерево и сохранить частичную упорядоченность значений приоритетов на дереве после удаления корня, выполняются следующие действия: на самом нижнем уровне находится самый правый узел и временно помещается в корень дерева. Затем этот элемент спускается по ветвям дерева вниз (на более низкие уровни), по пути меняясь местами с сыновьями, имеющими меньший приоритет, до тех пор, пока этот элемент не станет листом или не встанет в позицию, где его сыновья будут иметь по крайней мере не меньший приоритет.
Представление очереди с помощью массива, содержащего узлы частично упорядоченного дерева:
В массиве A первые n позиций соответствуют n узлам дерева. Элемент A содержит корень дерева. Левый сын узла дерева A [ i ], если он существует, находится в ячейке A , а правый сын, если он существует – в ячейке A . И наоборот, если сын находится в ячейке A [ i ], то его родитель в ячейке A [ i %2] . Узлы дерева заполняют ячейки A , A , … A [ n ] последовательно уровень за уровнем, начиная с корня, а внутри уровня – слева направо. Дерево, показанное выше, будет представлено в массиве следующей последовательностью своих узлов: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.
Упражнения:
1. Нарисуйте частично упорядоченное дерево, полученное в результате вставки в пустое дерево целых чисел 5, 6, 4, 9, 3, 1 и 7. Каков будет результат последовательного применения к этому дереву трех операторов DELETEMIN?
2. Реализуйте АТД “Очередь с приоритетами” для любого типа данных и его операторы INSERT, DELETEMIN и MAKENULL
§ частично упорядоченное дерево реализуется с помощью указателей,
§ частично упорядоченное дерево реализуется с помощью массива.
Раздел рабочей программы 2.1.3
Абстрактный тип данных " Объединение множеств".
АТД представляет собой объединение объектов, каждый из которых является множеством. Основные действия, выполняемые над такой совокупностью, заключаются в объединении множеств в определенном порядке, а также в проверке принадлежности определенного объекта конкретному множеству. Эти задачи решаются с помощью операторов MERGE (Слить) и FIND (Найти). Оператор MERGE(A , В, С ) делает множество С равным объединению множеств А и В , если эти множества не пересекаются (т. е. не имеют общих элементов); этот оператор не определен, если множества А и В пересекаются. Функция FIND(x ) возвращает множество, которому принадлежит элемент х; в случае, когда х принадлежит нескольким множествам или не принадлежит ни одному, значение этой функции не определено.
Операторы АТД “Объединение множеств”:
1. MERGE (A , В) объединяет компоненты А и. В, результат присваивается или А, или В.
2. FIND (x ) - функция, возвращающая имя компонента, которому принадлежит х.
3. INITIAL (A , х ) создает компонент с именем А, содержащим только элемент х.
Представление объединения множеств с помощью массивов:
Имя множества совпадает со значением индекса массива setheaders (имя 0)
Обозначения:
setheaders – массив заголовков множеств:
§ с ount – число элементов в множестве,
§ firstelement – индекс массива names с первым элементом множества,
names – массив списков элементов множеств:
- setname
- имя множества, которому принадлежит элемент,
nextelement
– индекс следующего элемента в списке данного множества (значение индекса 0 используется в качестве конца списка).
Раздел рабочей программы 2.1.3
Абстрактный тип данных “ Ориентированный граф”
Основные определения:
Ориентированный граф (орграф ) G = (V, Е) состоит из множества вершин V и множества дуг Е. Вершины также называются узлами , а дуги - ориентированными ребрами . Дуга представима в виде упорядоченной пары вершин (u , w ), где вершина и называется началом , a w - концом дуги.
Говорят также, что дуга и -> w ведет от вершины и к вершине w, а вершина w смежная с вершиной v .
Пример 1 орграфа:
Вершины орграфа можно использовать для представления объектов, а дуги - для отношений между объектами.
Путем в орграфе называется последовательность вершин v 1 , v 2 , … , vn , , для которой существуют дуги v 1 -> v 2 , v 2 , -> v 3, , ..., vn -1 , -> vn . Этот путь начинается в вершине v 1 и, проходя через вершины v 2 , v 3 , ..., vn -1 заканчивается в вершине vn . Длина пути - количество дуг, составляющих путь, в данном случае длина пути равна п - 1 . Как особый случай пути рассмотрим одну вершину v как путь длины 0 от вершины v к этой же вершине v . На рисунке последовательность вершин 1, 2, 4 образуют путь длины 2 от вершины 1 к вершине 4.
Путь называется простым , если все вершины на нем, за исключением, может быть, первой и последней, различны. Цикл - это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине. На рисунке вершины 3, 2, 4, 3 образуют цикл длины 3.
Во многих приложениях удобно к вершинам и дугам орграфа присоединить какую-либо информацию. Для этих целей используется помеченный орграф , т. е. орграф, у которого каждая дуга и/или каждая вершина имеет соответствующие метки. Меткой может быть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа.
Пример 2 помеченного орграфа:
DIV_ADBLOCK149">
3. Алгоритм транзитивного замыкания (алгоритм Уоршелла):
Для графа G = (V , E ) алгоритм вычисляет матрицу транзитивности T , каждый элемент которой T [i , j ] = 1 только тогда, когда существует путь от вершины i к вершине j и T [ i , j ] = 0 в противном случае.
4. Алгоритм нахождения центра орграфа:
Пусть и - произвольная вершина орграфа G = (V ,Е}. Эксцентриситет (максимальное удаление) вершины и определяется как
max{минимальная длина пути от вершины w до вершины v }
w V
Центром орграфа G называется вершина с минимальным эксцентриситетом. Другими словами, центром орграфа является вершина, для которой максимальное расстояние (длина пути) до других вершин минимально.
Пример: Центром орграфа является вершина d
Эксцентр-т |
||
| ||
5. Алгоритм обхода орграфа в глубину (поиска в глубину):
При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является так называемый поиск в глубину - обобщение метода обхода дерева в прямом порядке. Поиск в глубину начинается с выбора начальной вершины v графа G, эта вершина помечается меткой visited (посещалась). Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины v , будут "удостоены" посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G .
6. Алгоритм построения глубинного остовного дерева графа:
При обходе графа методом поиска в глубину только определенные дуги ведут к непосещённым вершинам. Такие дуги, ведущие к новым вершинам, называются дугами дерева и формируют для графа остовный лес, построенный методом поиска в глубину – глубинный остовный лес . При построении леса еще выделяются 3 типа дуг: обратные, прямые и поперечные.. Обратные дуги - такие дуги, которые в остовном лесе идут от потомков к предкам. Прямыми дугами называются дуги, идущие от предков к истинным потомкам, но которые не являются дугами дерева.
Дуги, соединяющие вершины, не являющиеся ни предками, ни потомками друг друга, называются поперечными дугами . Если при построении остовного дерева сыновья одной вершины располагаются слева направо в порядке их посещения и если новые деревья добавляются в лес также слева направо, то все поперечные дуги идут справа налево.
Например, дуги D ->С и G->D – поперечные, дуга C -> A – обратная, прямых дуг нет.
При глубинном обходе дерева часто удобно нумеровать вершины в порядке их посещения. Такие номера называются глубинными.
Представление орграфа:
§ Представление орграфа с помощью матрицы смежности:
Матрица смежности для орграфа G - это матрица А размером n n со значениями булевого типа, где A [ i , j ] = true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false - на 0.
Обобщением представления орграфа с помощью матрицы смежности можно считать представление помеченного орграфа также посредством матрицы смежности, но у которой элемент A [ i , j ] равен метке дуги i -> j . Если дуги от вершины i к вершине j не существует, то значение A[i , j ] не может быть значением какой-либо допустимой метки, а может рассматриваться как "пустая" ячейка.
Матрица смежности для помеченного орграфа (пример 2):
§ Представление орграфа с помощью списков смежности:
Списком смежности для вершины i называется список всех вершин, смежных с вершиной i , причем определенным образом упорядоченный. Орграф G можно представить посредством массива HEAD (Заголовок), чей элемент HEAD [i ] является указателем на список смежности вершины i .
 |
Операторы АТД “Орграф”:
Наиболее общие операторы, выполняемые над ориентированными графами, включают операторы чтения меток вершин и дуг, вставки и удаления вершин и дуг и оператор перемещения по последовательностям дуг.
Для просмотра множества смежных вершин необходимы следующие три оператора.
1. FIRST(v ) возвращает индекс первой вершины, смежной с вершиной v . Если вершина v не имеет смежных вершин, то возвращается "нулевая" вершина nil .
2. NEXT(v , i ) возвращает индекс вершины, смежной с вершиной v, следующий за индексом i. Если i - это индекс последней вершины, смежной с вершиной v, то возвращается nil .
3. VERTEX(v ,i ) возвращает вершину с индексом i из множества вершин, смежных с v .
Упражнения:
Дан ориентированный граф (орграф):
https://pandia.ru/text/78/308/images/image043_12.gif" width="125" height="100 src=">
Пример несвязного графа:
Циклом (простым) называется путь (простой) длины не менее 3 от какой-либо вершины до нее самой. Граф называется циклическим , если имеет хотя бы один цикл. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом . На втором рисунке, приведенном выше, показан граф, состоящий из двух связных компонент, каждая из которых является свободным деревом. Свободное дерево можно сделать "обычным" деревом, если какую-либо вершину назначить корнем, а все ребра сориентировать в направлении от этого корня.
Свободные деревья имеют два важных свойства:
1. Каждое свободное дерево с числом вершин n , n > 1 , имеет в точности n - 1 ребер.
2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл.
Пусть G = (V , Е) - связный граф, в котором каждое ребро (r , w ) помечено числом с(v , w), которое называется стоимостью ребра . Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево
Основные алгоритмы обработки неориентированных графов:
1. Построение остовного дерева минимальной стоимости (алгоритм Прима):
Строится множество вершин U , из которого "вырастает" остовное дерево. Пусть V= {1, 2, ..., n }. Сначала U = {1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (u , v ) такое, что u U и v V\U , затем вершина v переносится из множества V \ U в множество U . Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V .
Последовательность построения остовного дерева приведена ниже.
https://pandia.ru/text/78/308/images/image048_12.gif" width="501" height="384 src=">
3. Обход неориентированных графов методом поиска в глубину:
Для систематического обхода всех вершин графа используется поиск в глубину. Алгоритм поиска в глубину аналогичен алгоритму обхода вершин орграфа. Последний используется и для неориентированных графов, поскольку неориентированное ребро (v , w ) можно представить в виде пары ориентированных дуг v -> w и w -> v .
Обход в глубину можно использовать для построения остовного дерева.
Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину приведены ниже:
4. Обход неориентированных графов методом поиска в ширину
Другой метод систематического обхода вершин графа называется поиском в ширину . Он получил свое название из-за того, что при достижении во время обхода любой вершины v далее рассматриваются все вершины, смежные с вершиной v , т. е. осуществляется просмотр вершин "в ширину". Этот метод также можно применить и к ориентированным графам.
Так же, как и при применении поиска вглубь, посредством метода поиска в ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (х, у) вершина у не посещалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посещалась ранее, то ребро (х, у) будет поперечным ребром, так как оно соединяет вершины, не связанные наследованием друг друга.
Остовное дерево, полученное методом поиска в ширину показано ниже.
Представление неориентированного графа с помощью матрицы смежности:
Для представления неориентированных графов можно применять те же методы, что и для представления ориентированных графов, если неориентированное ребро между вершинами v и w рассматривать как две ориентированных дуги от вершины v к вершине w и от вершины w к вершине v.
https://pandia.ru/text/78/308/images/image051_12.gif" width="159" height="106">
Представление неориентированного графа с помощью списков смежности:
https://pandia.ru/text/78/308/images/image053_12.gif" width="339" height="115 src=">
1. Постройте:
остовное дерево минимальной стоимости посредством алгоритма Прима;
остовное дерево минимальной стоимости с помощью алгоритма Крускала;
остовное дерево методом поиска в глубину, начиная с вершин а и d;
остовное дерево методом поиска в ширину, начиная с вершин а и d.
2. Реализуйте алгоритмы Прима и Крускала.
3. Реализуйте построение остовного дерева методом поиска в глубину
§ для неориентированного графа представленного с помощью матрицы смежности,
§ для неориентированного графа представленного с помощью списков смежности.
4. Реализуйте построение остовного дерева методом поиска в ширину
§ для неориентированного графа представленного с помощью матрицы смежности,
§ для неориентированного графа представленного с помощью списков смежности.
