Графы и их представление

Лекция 3 Графы и их представление Краткая теория Графом G называют пару конечных множеств G=(V , E) , где элементы множества V называются вершинами, а элементы множества E представляют из себя пары элементов из множества V и называются рёбрами. Если рёбра в графе представляют из себя неупорядоченные пары {u , v} , то соответствующий граф называют неориентированным. Если рёбра – упорядоченные пары (u , v) , то граф называют ориентированным (орграфом). В случае орграфов рёбра также называют дугами. Говорят также, что вершины u и v соединены ребром. Матрица инцидентности содержит информацию об инцидентности вершин рёбрам. Один из индексов в этой матрице является номером ребра, а другой – номером вершины. Если вершина i инцидентна ребру j, то в соответствующий элемент матрицы с индексом (i,j) содержит 1, в противном случае – 0. Список рёбер представляет из себя простое перечисление рёбер с указанием инцидентных им вершин. Обычно список рёбер используется для хранения графа в файле. В этом случае часто рёбра не нумеруются явно. Эйлеровым циклом называется цикл, проходящий по каждому ребру графа ровно один раз. Соответственно, граф, содержащий такой цикл, называется эйлеровым. Сформулируем критерий эйлеровости графа: Связный неориентированный граф содержит эйлеров цикл тогда и только тогда, когда число вершин нечётной степени равно нулю. Для ориентированных графов формулировка теоремы несколько иная: ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна степени её выхода. Если эйлеров цикл в графе существует, то это означает, что следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от неё карандаша. Пусть дан неориентированный граф G, удовлетворяющий условию теоремы Эйлера. Рассмотрим алгоритм нахождения эйлерова цикла в этом графе. Этом алгоритм основан на обходе графа в глубину. При переходе в очередную вершину будем удалять соответствующее, пройденное ребро. При обнаружении вершины, из которой не выходят рёбра (мы их удалили раннее при обходе в глубину), будем записывать её номер в стек. Обнаружение вершины с нулевым числом рёбер говорит о том, что найден цикл. Его можно удалить, при этом чётность степеней вершин не изменится. Процесс продолжается до тех пор, пока есть не пройденные рёбра. После окончания обхода в глубину всего графа в стеке будут записаны номера вершин графа в порядке, соответствующем эйлерову циклу. Euler: Вход: граф Graph, представленный матрицей смежности; стек вершин эйлерова цикла Stack, номер стартовой вершины U. Начало. Для всех вершин V графа Graph, смежных с U: Graph[U,V] := 0, Graph[V,U] := 0. Euler(Graph, Stack, V). Помещаем в Stack вершину U. Конец. Задание 3. 1)Создать класс в соответствии с вариантом, реализующий граф. 2) В качестве внутреннего представления графа использовать метод в соответствие с Вариант представления графа 1) МС – Матрица смежности 2) МИ – Матрица инцидентности 3) СС – Список смежности 4) СР – Список ребер № Входной формат Внутреннее представление МС МИ СС СР МС МИ СС СР 16 * * 3) В качестве входного параметра передавать одно из представлений графа, выбираемое в соответствие с вариантом из пункта 5.1. 4) Реализовать один из алгоритмов обработки графа, выбираемый в со-ответствие с Вариант реализуемых алгоритмов а) Поиск Эйлерова цикла в графе 5) Создать проект для автоматизации тестирования и создать набор те-стов для проверки работы класса. 6) Запустить проект тестирования и проверить результаты его работы. Лекция 7.1 Циклическая очередь Для решения проблемы с исчерпанием ячеек при вставке новых элементов в очередь, в которой имеются свободные ячейки в начале массива, маркеры head и tail при достижении границы массива перемещается к его началу (этот способ работы с массивом обозначается термином кольцевой буфер). Такая структура данных будет называться циклической очередью (рисунок 2.6). 53 Рисунок 2.6 – Циклическая очередь Один из способов, который позволяет реализовать очередь, состоя-щую не более чем из (n-1) элементов является массив Q[1..n]. Эта очередь обладает атрибутом head[Q], который является индексом головного эле-мента или указателем на него; атрибут tail[Q] индексирует местоположение, куда будет добавлен новый элемент. Для исключения ситуации, когда невозможно определить, пуста очередь или заполнена, необходимо пожертвовать одним элементом очереди. Он будет являться своего рода разделителем или барьером между головным элементом и хвостом очереди. Элементы очереди расположены в ячейках head[Q], head[Q] +1,..., tail[Q] - 1, которые циклически замкнуты в том смысле, что ячейка 0 следует сразу же после ячейки n в циклическом порядке. При выполнении условия head[Q] = tail[Q] очередь пуста. Изначально выполняется соотношение head[Q] = tail[Q] = 0. Если очередь пустая, то при попытке удалить из нее элемент происходит ошибка опустошения. Если head[Q] = tail[Q] + l, то очередь заполнена, и попытка добавить в нее элемент приводит к ее переполнению. Операции, производимые над очередью (с примерами реализации на псевдокоде): 1) Вставка элемента в очередь (Enque). Q[tail[Q]] <- х if (tail[Q] = length[Q]) then tail[Q] <- 0 else tail[Q] <- tail[Q] + 1 54 2) Извлечение элемента из очереди (Deque). x <- Q[head[Q]] if (head[Q] = length[Q]) then head[Q] <- 0 else head[Q] <- head[Q] + 1 return x 3) Прочтение первого элемента без его выборки из очереди (Peek). x <- Q[head[Q]] 4) Проверка очереди на пустоту (Empty). if (tail[Q] = head[Q]) then return true else return false 5) Проверка очереди на переполнение (Full). if (head[Q] = (tail[Q] + 1)%N) then return true else return false 6) Свойство для определения количества элементов (Count). return (tail[Q] - head[Q]) if (head[Q] > tail[Q]) then return (N - head[Q] + tail[Q]) else return (tail[Q] - head[Q]) 7.2 Дек Дек (deque) представляет собой двустороннюю очередь. И вставка, и удаление элементов могут производиться с обоих концов. Соответствующие методы могут называться PushFront/PushBack (InsertLeft/InsertRight) и PopFront/PopBack (RemoveLeft/RemoveRight). Если ограничиться только методами PushBack и PopBack (или их эквивалентами для правого конца), дек работает как стек. Если же ограничиться методами PushBack и PopFront (или противоположной парой), он работает как очередь. По своей гибкости деки превосходят и стеки, и очереди; иногда они используются в библиотеках классов-контейнеров для реализации обеих разновидностей. Рисунок 7.2 – Дек Задание 6. Полустатические структуры данных (консольное приложение) 1. Создать класс в соответствии с вариантом, реализующий один из видов АТД. 2.) Создать проект для автоматизации тестирования и создать набор тестов для проверки работы класса. 3.) Запустить проект тестирования и проверить результаты его работы. Тип хранимых элементов АТД int double string char long float Циклическая очередь 10 17 3 15 5 22