Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Машинное представление графа ⇐ ПредыдущаяСтр 2 из 2
Приведем вначале сравнительную характеристику существующих способов представления графа в памяти ЭВМ, их достоинства и недостатки. Рассмотрим конечный граф G =(V, E), где | V |= n, | E |= m. Матрица инциденций. Ориентированный граф задается прямоугольной матрицей B (n ´ m), элементы которой определяются по правилу: где a – любое натуральное число, отличное от 1. У неориентированного графа оба элемента матрицы, соответствующие вершинам, инцидентным ребру ej, равны 1. Это представление графа является самым неудобным, так как объем занимаемой памяти равен n×m единиц, причем в каждом столбце только две ненулевые ячейки. Кроме нерационального использования памяти недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы: а) существует ли ребро (дуга) (vi, vj); б) к каким вершинам ведут ребра (дуги) из вершины vi требуется, в худшем случае, перебор n×m элементов, т.е. порядка n×m шагов алгоритма. От этого недостатка свободен следующий способ представления графа. Матрица смежности. Элементы квадратной матрицы A (n ´ n) определяются следующим образом: Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n 2 шагов алгоритма. При этом способе объем неиспользованной памяти по-прежнему велик. Заметим, что для сокращения объема используемой памяти возможно использование 1-го бита для хранения элемента aij, но при этом, выигрывая в памяти, мы затрудняем доступ к информации. В этом случае придется применять операции для работы с битами информации, используя различные маски. При работе со взвешенными графами для хранения весов ребер (дуг) требуются дополнительные одномерные массивы размера m (для случая матрицы инциденций) или матрицы размера n ´ n (для случая матрицы смежности). Это обстоятельство делает неприемлимым использование матрицы смежности для взвешенных графов, так как количество неиспользованных единиц памяти увеличивается в k раз, где k – число весов ребер (дуг). Съэкономить объем используемой памяти можно, применяя представление графа в виде Таблицы ребер.
Она представляет собой матрицу размером m ´2, каждая строка которой содержит вершины инцидентные i -му ребру (i -ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг). Однако, этому способу представления графа присущ тот же недостаток, что и матрице инциденций, - неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Поиск можно ускорить, введя лексикографический порядок в упорядочении пар и применяя двоичный поиск. Наиболее удобной и экономичной формой представления графа являются Списки инцидентности. Для каждой вершины vi Î V создается список записей, характерезующих ребра (дуги), инцидентные этой вершине. Таким образом, это представление использует объем памяти порядка (n + m), поиск вершины смежной с данной требует порядка (n + m) шагов, проверка свойств графа осуществляется за число шагов порядка. Поэтому остановимся подробнее на этом способе задания графа. Каждая запись содержит две части: информационную и ссылочную. В информационную часть включаются поля: а) вершина vj, смежная с вершиной vi; б) веса ребер (дуг) при работе со взвешенными графами; в) другая вспомогательная информация о ребре (дуге), если это необходимо для работы с графом. Ссылочная часть содержит: а) ссылку на следующую запись списка; б) ссылку на предыдущую запись списка (для двунаправленных списков); в) ссылку на запись, содержащую вершину vi, в списке инцидентности вершины vj (для неориентированного графа). Типы «запись» и «ссылка на запись» должны быть предварительно описаны в программе. Например, описание type ref = Ù Elem; Elem = record num: integer; ves: array [1.. kv] of real; sled, pred, ref_vi: ref; end; определяет запись, характерезующую ребро взвешенного неориентированного графа с числом весов kv, и ссылку на эту запись (типизированный указатель). В данном примере используется двунаправленные списки. Ссылки на первую запись каждого списка хранятся в массиве, размер которого равен числу вершин графа. В программе должна быть описана переменная типа «массив», элементы которого имеют тип «ссылка на запись». Например,
var mas_ref: array [1.. n] of ref; Если вершина vi является изолированной, то mas_ref [vi]= nil. Структуру представления графа в памяти ЭВМ можно схематично представить следующим образом:
Рис. 1 На этом рисунке изображены фрагменты списков инцидентности неориентированного графа, соответствующие ребру графа . У ориентированного графа в каждой записи будет отсутствовать третье ссылочное поле, и не будет дублирования в списке инцидентности конечной вершины дуги. Например, неориентированный граф
Рис. 2 имеет cледующее представление в памяти Для ориентированных графов могут формироваться как списки вершин, следующих за текущей, так и предшествующих ей вершин. Для формирования машинного представления графа необходимо сформировать список инцидентности для каждой вершины графа и заполнить массив ссылок на эти списки. Формирование списка инцидентности может осуществляться по принципу стека (LIFO), когда новая запись включается в начало списка, или по принципу очереди (FIFO), когда новая запись ставится в конец списка. Напомним, что для включения записи в список нужно выделить область динамической памяти, соответствующую размеру записи, и заполнить ее поля. При работе с графом часто требуется выполнить действия, изменяющие его структуру. К ним относятся: 1. Добавление ребра (дуги) (vi, vj) в граф G. Для этого нужно: а) добавить запись с вершиной vj в список инцидентности вершины vi; б) для неориентированного графа добавить запись с вершиной vi в список инцидентности вершины vj. 2. Удаление ребра (дуги) (vi, vj) из графа G (осуществляется аналогично добавлению ребра (дуги)). 3. Удаление вершины vi из графа G. Для этого нужно удалить все ребра (дуги) инцидентные вершине vi (т.е. удалить все записи из списка вершины vi, а для неориентированных графов – и соответствующие записи из списков смежных с ней вершин) и изменить ссылку в массиве ссылок на списки инцидентности mas_ref [vi]= nil. Часто кроме изменения структуры графа для более эффективной работы алгоритмов требуется сортировка (упорядочение) списков инцидентности. При этом применяются известные алгоритмы сортировки, следует лишь заметить, что при изменении порядка записей в списке изменяются только поля sled, pred в записях списка. Ввод графа осуществляется из текстового файла одного из двух видов: «таблица смежности» или «таблица ребер». Такие файлы по-разному формируются и интерпретируются для неориентированных и ориентированных графов: для неориентированного графа задаются ребра графа, а для ориентированного – дуги. То есть, ребро неориентированного графа задается один раз, а соответствующие ему записи автоматически включаются в списки инцидентности обоих его концов. Файл «таблица смежности» состоит из блоков, соответствующих вершинам графа. Каждый блок имеет следующую структуру: начальная вершина: список смежных с ней вершин соответствующие ребрам веса Количество строк с весами ребер равно kv, число вершин списка равно числу весов в строках. Блоки в таком файле могут располагаться в произвольном порядке, причем, если вершина не является начальной ни для одного ребра (дуги) или ребро уже включено в список инцидентности другого его конца, то соответствующий ей блок может отсутствовать в файле.
Например, файл «таблица смежности» графа, изображенного на рис.2 имеет вид v1: v3 v4 5 10 v3: v4 v4: v5 4, а ориентированный граф
Рис.4 задается «таблицей смежности» 1: 2 3 2: 3 3: 1 Файл «таблица ребер» имеет следующую структуру: начальные вершины ребер (дуг) конечные вершины ребер (дуг) веса ребер (дуг) Также как и для «таблицы смежности» количество элементов в каждой из строк должно быть одинаковым, а число весов равно kv. Если строка данных не умещается на экран монитора, то для удобства просмотра файла можно перенести оставшиеся части ниже в том же порядке, отделив одну часть от другой пустой строкой. Например, файл «таблица ребер» графа, изображенного на рис.2 имеет вид. v1 v1 v4 v4 v4 v3 v3 v5 10 5 7 4 Вывод списков инцидентности графа на экран или в файл осуществляется в соответствии со структурой аналогичной файлу «таблица смежности». При этом просматривается список каждой вершины, если он непуст, то выводится: СП, затем в скобках вершина,:, список вершин смежных с ней. Например, выводимая информация имеет вид: а) для графа (рис.2) СП(v1): v3 v4 СП(v3): v1 v4 СП(v4): v1 v3 v5 СП(v5): v4; б) для графа (рис.4) Списки следования: Списки предшествования: СП [1]: 2 3 СП [1]: 3 СП [2]: 3 СП [2]: 1 СП [3]: 1 СП [3]: 2 1.
Задание для самостоятельной работы.
I. Написать и отладить программу в соответствии с вариантом задания №1 (см. приложение). Такая программа должна содержать: 1) ввод исходного графа из файла заданного вида и формирование для него списков инцидентности; 2) подсчет и вывод количества вершин и ребер (дуг), вывод списков инцидентности исходного графа; 3) выполнение индивидуального задания варианта и вывод его результатов. II. Продемонстрировать работу программы на контрольном примере. III. Текст программы, граф и исходный файл контрольного примера, результаты работы программы оформить в отчет.
Варианты заданий По таблице смежности построить списки инцидентности неориентированного графа и подсчитать степени его вершин. По таблице рёбер построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин. По таблице смежности построить списки инцидентности ориентированного графа и подсчитать полустепени его вершин. По таблице рёбер построить списки инцидентности неориентированного графа и подсчитать степени его вершин. По таблице смежности построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин.
По таблице рёбер построить списки инцидентности неориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин. По таблице смежности построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по убыванию номеров вершин. По таблице рёбер построить списки инцидентности ориентированного графа, записи в каждом списке упорядочить по возрастанию номеров вершин. По таблице смежности построить списки инцидентности неориентированного графа, удалить из графа все рёбра, начинающиеся и заканчивающиеся в вершинах n1, n2, n3 или n4. По таблице рёбер построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах, кратных 2, и концом в вершинах, кратных 5. По таблице рёбер построить списки инцидентности ориентированного графа, удалить из графа вершины с номерами n1 и n2. По таблице смежности построить списки инцидентности ориентированного графа, добавить рёбра с началом в вершинах n1, n2 и n3 и концом в вершинах n3, n4 и n5. По таблице рёбер построить списки инцидентности неориентированного графа, удалить из графа все рёбра, обе вершины которых кратны 3.
|
|||||||||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 371; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.119.133.228 (0.028 с.) |