Представление графов в памяти компьютера
Конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Далее приводится четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.
1.4.1 Требования к представлению графов
Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) — объема памяти для каждого представления. Здесь p — число вершин, а q — число ребер.
1.4.2 Матрица смежности
Представление графа с помощью квадратной булевой матрицы M, отражающей смежность вершин, называется матрицей смежности, где
Для матрицы смежности n(p,q) = O(p 2 ).
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.
1.4.3 Матрица инциденций
Представление графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
Для матрицы инциденций n(p,q) = O(pq).
1.4.4 Списки смежности
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей на списки смежных вершин, где элемент списка представлен структурой
N : record v : 1..p; n :^ N end record,
называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q).
1.4.5 Массив дуг
Представление графа с помощью массива структур
E : array [1..q] of record b,e : 1..p end record,
отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q).
Представление графов в памяти компьютера
Представление графов в памяти компьютера существенно зависит от типов структур данных, допускаемых используемым алгоритмическим языком и типом компьютера. Представление с помощью матрицы смежности ‑ одно из самых распространенных. Для графов с большим числом дуг это достаточно компактное представление, особенно если есть возможность работать с двоичными битами в машинном слове. К недостаткам следует отнести большой расход памяти при работе с графами, имеющими небольшое число дуг (матрица смежности при этом получается весьма разреженной), а также невозможность уменьшения трудоемкости алгоритмов в том случае, когда она пропорциональна числу дуг, а не числу вершин.
Матрица смежности неориентированного графа симметрична относительно главной диагонали, поэтому достаточно хранить в памяти только половину ее.
Задание графа с помощью матрицы смежности удобно и тогда, когда граф взвешенный и элементами матрицы являются не нули и единицы, а веса дуг. Пример задания ориентированного и неориентированного графов матрицами смежности приведен на рис. 4.2.
Рис. 4.2. Задание ориентированного и неориентированного графов матрицами смежности.
Представление с помощью матрицы инциденций определяет граф однозначно (с точностью до изоморфизма), но применяется крайне редко в силу большой разреженности матрицы и практического отсутствия алгоритмов, работающих на такой структуре данных.
Представление с помощью списков смежности является основной альтернативой представлению с помощью матрицы смежности. Список смежности для вершины v ‑ это список концов дуг, исходящих из вершины в случае орграфа, или список смежных с вершин в случае графа. Граф представляется с помощью списков смежности, по одному для каждой вершины. Если число дуг в орграфе существенно мало по сравнению с полным графом, то этот сподоб представления весьма эффективен. Списки смежности занимают объем памяти и легко реализуются с помощью списочных структур. Менее удобен этот способ представления для задания взвешенных графов, так как тогда возникает необходимость хранения весов дуг и установления соответствующих связей между дугами и их весами.
Пример задания графов, показанных на рис. 4.2, с помощью списков смежности приведен на рис. 4.3. Представление с помощью списка дуг применяется в тех случаях, когда необходимо иметь отдельную, независимую нумерацию дуг. При этом способе каждой дуге сопоставляется тройка , где ‑ дуга, ‑ ее начало, ‑ ее конец. Этот способ представления легко обобщается на случай взвешенных графов. Более того, он наиболее приспособлен для хранения различной информации о дугах.
Пусть ‑ неориентированный граф, ‑ его матрица смежности. Так как симметрична относительно главной диагонали, будем рассматривать только ее верхнюю треугольную часть . Запишем строки последовательно одну за другой и найдем двоичное число, соответствующее полученной последовательности из нулей и единиц. Меняя нумерацию вершин, будем для одного и того же графа получать разные числа. Наибольшее из них носит название кода Xapapи.
Рис. 4.3. Списки смежности графов на рис. 4.2.
Код Харари определяет граф однозначно, поэтому, например, задачу определения изоморфизма двух графов можно свести к сравнению соответствующих кодов Харари[3].
Нумерация вершин (и матрица смежности), соответствующая коду Харари, носит название канонической и используется при перечислении (генерировании) графов с заданными свойствами.
Наиболее распространенным методом сбора информации о строении графа является специальным образом организованный обход вершин и дуг (ребер) графа [5]. Информация, получаемая таким способом, оформляется в виде подходящей нумерации вершин.
Дата добавления: 2016-06-05 ; просмотров: 4296 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Представление графов в памяти компьютера
Графом называется пара (V,E), где V — конечное множество вершин, а E — набор неупорядоченных и упорядоченных пар вершин. Обозначим граф G=(V,E). Неупорядоченная пара вершин называется ребром, упорядоченная — дугой. Граф содержащий только ребра называется неориентированным, только дуги — ориентированным, или орграфом.
Если вершины v и u соединены ребром e, то говорят, что они смежны между собой, а ребро e инцидентно каждой из них. Количество ребер графа, инцидентных вершине v называется степенью данной вершины. Для ориентированного графа выделяют входящую степень, равную количеству входящих ребер и исходящую степень, равную количеству исходящих ребер, а степенью вершины в таком случае называют сумму ее входящей и исходящей степени. Вершины имеющие степень 0 называют изолированными.
Для орграфа на рис.3 входящие степени вершин 1,2,3,4,5 равны соответственно 0,1,1,1,0, исходящие — 2,0,0,1,0. Степени вершин, получаемые сложением входящих и исходящих степеней равны 2,1,1,2,0. Таким образов, вершина 5 — изолированная.
Ребро, соединяющее вершину саму с собой называется петлей. Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными. Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями — псевдографом.) Простой граф, любая пара вершин которого соединена ребром, называется полным. В полном графе n*(n-1)/2 ребер.
Граф называется разреженным, если общее количество ребер значительно меньше их возможного количества. Иначе граф называется плотным.
Подграфом графа G=(V,E) называется граф G’=(V’,E’) такой, что V’⊆V, E’⊆E.
Путем из вершины u в вершину x называется последовательность вершин (v0,v1. vk), в которой v0=u, vk=x и (vi-1,vi) ∈ E. Длина этого пути равна k. Такой путь проходит через вершины v0,v1. vk, а также ребра (v0,v1), (v1,v2). (vk-1,vk). Вершина v0 — начало пути, vk — конец пути. Говорят, что путь ведет из v0 в vk. Если существует путь из вершины u в вершину x, говорят, что x достижима из u.
Пример. На рис.4 последовательность вершин (5,1,3,4) является путем.
Путь называется простым, если он содержит каждую из вершин не более одного раза.
Неориентированный граф называется связным, если существует хотя бы один путь между каждой парой вершин, и несвязным в противоположном случае.
Ориентированный граф связен, если связен неориентированный граф, получаемый из этого орграфа снятием ориентации с дуг. Ориентированный граф сильно связен, если для любой пары вершин v и u существут путь из v в u и из u в v.
Связной компонентой графа называется максимальный связный подграф этого графа. Сильно связной компонентой называется максимальный сильно связный подграф.
Циклом называется путь из некоторой вершины в эту же вершину, содержащий хотя бы одно ребро. Цикл простой, если в нем нет повторяющихся вершин (за исключением начальной (конечной), которая является первой и последней вершиной пути).
Граф, в котором нет циклов называется ациклическим.
Связный граф без циклов называется деревом.
Граф называется двудольным, если множество его вершин V можно разбить на непересекающиеся подмножества V1 и V2 так, что никакие две вершины одного подмножества не смежны. Пример двудольного графа на рис. 5.
Графы G1=(V1,E1) и G2=(V2,E2) изоморфны, если существует такое взаимно однозначное отображение ƒ:V1→V2, что для произвольных v и u∈V1 имеем (v,u)∈E1⇔(ƒ(v),ƒ(u))∈E2. Отображение ƒ называется изоморфизмом (или изоморфным отображением) графов G1 и G2. При изоморфизме каждая вершина переходит в вершину с той же степенью. Пример изоморфных графов на рис.6 (1->2, 2->4, 3->5, 4->3, 5->1).
Любой граф можно представить множеством точек на плоскости, соответствующих вершинам, соединенных линиями, соответствующими ребрам. В трехмерном пространстве граф всегда можно представить таким образом, что эти линии не будут пересекаться.
При разработке эффективных алгоритмов выбор структуры данных имеет принципиальное значение. Рассмотрим три основных структуры.
Список ребер
Наиболее очевидный способ — хранить список пар вершин, соединенных ребрами. Для его хранения необходим двумерный массив размерности Mx2 (M — количество ребер). Строка массива описывает ребро. Для взвешенных графов такой способ создает необходимость дополнительно завести массив весов ребер.
Пример для орграфа на рис.4:
| e1 | e2 | e3 | e4 | e5 | |
| v1 | 5 | 1 | 1 | 3 | 1 |
| v2 | 1 | 2 | 3 | 4 | 4 |
Матрица смежности.
Матрица смежности A представляет собой двумерный массив размерности NxN (N — количество вершин). A[i,j]=1, если существует ребро (i,j) (дуга ), A[i,j]=0 — в противном случае. Для неориентированных графов матрица смежности симметрична относительно главной диагонали.
Для взвешенных графов значение элемента A[i,j] обычно используют для хранения веса соответствующего ребра. Для невзвешенных мультиграфов A[i,j] может содержать количество ребер, соединяющих вершины i и j.
Пример. Матрица смежности для графа на рис.7:
| v1 | v2 | v3 | v4 | v5 | |
| v1 | 0 | 1 | 1 | 1 | 1 |
| v2 | 1 | 0 | 0 | 0 | 0 |
| v3 | 1 | 0 | 0 | 1 | 0 |
| v4 | 1 | 0 | 1 | 0 | 0 |
| v5 | 1 | 0 | 0 | 0 | 0 |
Список связей
Третий способ — хранение списка всех ребер инцидентных каждой из вершин. Для этого необходим массив, содержащий N элементов, где N — количество вершин в графе. i-ый элемент этого массива содержит список всех ребер, смежных с i-ой вершиной (ребро представлено номером второй инцидентной ему вершины).
Способы представления графов в памяти
Многие объекты, возникающие в жизни человека, могут быть смоделированы (представлены в памяти компьютера) при помощи графов. Например, транспортные схемы (схема движения троллейбусов и т. д.) изображают в виде станций, соединенных линиями. В терминах графов станции называются вершинами графа, а линии – ребра.
Графом называется конечное множество вершин и множество ребер. Каждому ребру сопоставлены две вершины – концы ребра.
Бывают различные варианты определения графа. В данном определении концы у каждого ребра – равноправны. В этом случае нет разницы где начало, а где – конец у ребра. Но, например, в транспортных сетях бывают случаи одностороннего движения по ребру, тогда говорят об ориентированном графе – графе, у ребер которого одна вершина считается начальной, а другая – конечной.
Если некоторое ребро u соединяет две вершины A и B графа, то говорят, что ребро u инцидентно вершинам A и B, а вершины в свою очередь инцидентны ребру u. Вершины, соединенные ребром, называются смежными.
Ребра называются кратными, если они соединяют одну и ту же пару вершин (а в случае ориентированного графа – если у них совпадают начала и концы). Ребро называется петлей, если у него совпадают начало и конец. Во многих задачах кратные ребра и петли не представляют интереса, поэтому могут рассматриваться только графы без петель и кратных ребер. Такие графы называю простыми.
Степенью вершины в неориентированном графе называется число инцидентных данной вершине ребер (при этом петля считается два раза, то есть степень — это количество «концов» ребер, входящих в вершину). Довольно очевидно, что сумма степеней всех вершин равна удвоенному числу ребер в графе. Отсюда можно посчитать максимальное число ребер в простом графе — если у графа n вершин, то степень каждой из них равна n−1, а, значит, число ребер есть n(n−1)/2. Граф, в котором любые две вершины соединены одним ребром, называется полным графом.
Также легко заметить следующий факт – в любом графе число вершин нечетной степени – четно. Этот факт называется «леммой о рукопожатиях» – в любой компании число людей, сделавших нечетное число рукопожатий всегда четно.
Пути, циклы, компоненты связности
Путем на графе называется последовательность ребер u1, u2, …, uk, в которой конец одного ребра является началом следующего ребра. Начало первого ребра называется началом пути, конец последнего ребра — концом пути. Если начало и конец пути совпадают, то такой путь называется циклом.
Путь, который проходит через каждую вершину не более одного раза называется простым путем. Аналогично определяется простой цикл.
Граф называется связным, если между любыми двумя его вершинами есть путь. Если граф несвязный, то его можно разбить на несколько частей (подграфов), каждая из которых будет связной. Такие части называются компонентами связности. Возможно, что некоторые компоненты связности будут состоять всего лишь из одной вершины.
Понятно, что в графе из n вершин может быть от 1 до n компонент связности.
Способы представления графов в памяти
Граф может быть представлен (сохранен) несколькими способами:
· список смежности (инцидентности);
Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Размер массива зависит от количества вершин и/или ребер в конкретном графе.
Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.
Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа.
· 0 – соответствует отсутствию ребра,
· 1 – соответствует наличию ребра.
Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0 если граф не имеет петель.
Матрица инцидентности (инциденции) графа — это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро(дуга) и вершина).
В неориентированном графе если вершина инцидентна ребру то соответствующий элемент равен 1, в противном случае элемент равен 0.
В ориентированном графе если ребро выходит из вершины, то соответствующий элемент равен 1, если ребро входит в вершину, то соответствующий элемент равен -1, если ребро отсутствует, то элемент равен 0.
Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно.
Список смежности (инцидентности)
Если количество ребер графа по сравнению с количеством вершин невелико, то значения большинства элементов матрицы смежности будут равны 0. При этом использование данного метода нецелесообразно. Для подобных графов имеются более оптимальные способы их представления.
По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк — не больше, чем вершин в графе.
В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины.
Преимущества списка смежности:
· Рациональное использование памяти.
· Позволяет быстро перебирать соседей вершины.
· Позволяет проверять наличие ребра и удалять его.
Недостатки списка смежности:
· При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.
· Нет быстрого способа проверить, существует ли ребро между двумя вершинами.
· Количество вершин графа должно быть известно заранее.
· Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:
o номер вершины, с которой соединяется текущая;
Список рёбер
В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).
Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер.
Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными, с малым — разреженными. Плотные графы удобнее хранить в виде матрицы смежности, разреженные — в виде списка смежности.
Алгоритмы обхода графов
Основными алгоритмами обхода графов являются
· Поиск в глубину
Поиск в ширину подразумевает поуровневое исследование графа:
· вначале посещается корень – произвольно выбранный узел,
· затем – все потомки данного узла,
· после этого посещаются потомки потомков и т.д.
Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:
· 0 — оранжевый – необнаруженная вершина;
· 1 — зеленый – обнаруженная, но не посещенная вершина;
· 2 — серый – обработанная вершина.
Фиолетовый – рассматриваемая вершина.
Применения алгоритма поиска в ширину
· Поиск кратчайшего пути в невзвешенном графе (ориентированном или неориентированном).
· Поиск компонент связности.
· Нахождения решения какой-либо задачи (игры) с наименьшим числом ходов.
· Найти все рёбра, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
· Найти все вершины, лежащие на каком-либо кратчайшем пути между заданной парой вершин.
Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.
Для реализации алгоритма удобно использовать очередь.
Перечень документов по охране труда. Сроки хранения: Итак, перечень документов по охране труда выглядит следующим образом.
Способы представления графов в памяти ЭВМ
Для представления графов можно использовать различные структуры данных. Выбор структуры данных зависит от операторов, которые будут применяться к вершинам и ребрам (дугам) графа.
5.2.1.Матрица смежностей графа
Одним из наиболее общих представлений орграфа G = (V, Е) является матрица смежности. Предположим, что множество вершин V= . Матрица смежности для орграфа G — это матрица размера n х n со значениями булевого типа, где A[i,j] = true тогда и только тогда, когда существует дуга из вершины i в вершину j. Часто в матрицах смежности значение true заменяется на 1, а значение false — на 0. Время доступа к элементам матрицы смежности зависит от размеров множества вершин и множества дуг. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто проверять существование данной дуги. Для мультиграфа вместо 0 или 1 указывается число, равное кратности ребер. На рис. 12 показаны матрицы смежностей: для орграфа на рис. 1,а – а, для неорграфа на рис. 11,б – б, для мультиграфа на рис. 2,а – в, для наглядности вместо 0 стоит «пустая ячейка.
Если граф не имеет петель, то на диагонали матрицы расположены нули. Для неорграфа матрица симметрична относительно главной диагонали и сумма элементов матрицы в каждой строке и в каждом столбце равна степеням соответствующих вершин.
Если на вершинах графа заданы веса, вводится дополнительный массив V длиной N, где элемент vi содержит значение веса вершин графа с номером i.
Если на ребрах (дугах) заданы веса, то для неорграфа и орграфа применяется матрица, совпадающая со структурой матрицы смежностей, но значения элементов равны весам соответствующих связей.
Для мультиграфов и псевдографов с весами на ребрах и петлях используется трехмерная матрица, имеющая структуру строк и столбцов, аналогичную структуре матрицы смежностей, а третья размерность применяется для записи веса каждого ребра, дуги, петли.
5.2.2. Матрица инцидентностей графа
Матрица инцидентностей – прямоугольная матрица В, строки которой соответствуют вершинами, а столбцы – ребрам (дугам) графа. Для неорграфа:
Число единиц в i-й строке равно степени вершины vi графа, а число единиц в любом столбце – 2.
Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец содержит один элемент, равный 1, и один – равный –1, либо все элементы столбца равны 0.
Если на вершинах графа заданы веса, то используется дополнительный массив V длиной N, где элемент vi имеет значение веса вершины графа с номером i, если на ребрах (дугах) заданы веса, то – дополнительный массив W длиной q, где элемент wi содержит значение веса ребра (дуги).
На рис. 13 показаны матрицы инцидентностей для орграфа на рис. 1,а – а, для неорграфа на рис. 11,б – б.
5.2.3. Задание графа массивом преемников вершин
(FO-представление графа)
В целях экономичного представления графа в памяти ЭВМ часто используют FO -представление графа, позволяющее отобразить матрицу смежностей графа одномерным массивом FO, формирующимся следующим образом: сначала записываются номера вершин (в любом порядке), в которые заходят дуги из первой вершины, затем ставится разделитель 0, далее – номера вершин, в которые заходят дуги из второй вершины, после чего ставится разделитель 0 и т.д. Таким образом, для неорграфа и мультиграфа строится массив FO длиной 2xq+N, так как каждое ребро учитывается дважды, для орграфа и псевдографа – массив FO длиной q+N. Будем считать, что величины N и q заданы и на их основе построен массив FO. Если на вершинах и (или) ребрах (дугах) заданы веса, то применяются дополнительные массивы V(N) и W(q), где элементы vi и wj содержат значения весов для вершин vi и ребра (дуги) lj.
Например, одномерный массив FO для орграфа на рис. 1,а имеет вид: , а для неорграфа на рис. 11,б:
5.2.4. Задание графа массивом предшественником вершин
(FI-представление)
Массив FI формируется так: сначала записывают номера вершин (в любом порядке), из которых исходят дуги в первую вершину, затем ставят разделитель 0, далее записывают номера вершин, из которых исходят дуги во вторую вершину, и ставят разделитель 0 и т.д. Таким образом, для неорграфа и мультиграфа строится массив FI длиной 2xq+N, так как каждое ребро учитывается дважды. Для орграфа и псевдографа массив FI имеет длину q+N. Заметим, что для неорграфов и мультиграфов FO и FIпредставления совпадают.
Например, одномерный массив FI для орграфа на рис. 1,а имеет вид: .
5.2.5. Модифицированное FO-представление графа
(MFO-представление)
В MFO -представлении графа вместо разделителей 0 используется дополнительный массив P длиной N, в котором указываются верхние границы окончания списков номеров вершин в массиве G, смежных с заданной вершиной по выходящим дугам. Для неорграфов и мультиграфов длина массива G равна 2xq, а массива P – N. Для орграфов и псевдографов длина массива G равна q, а массива P – N.
Для хранения весов вершин и ребер (дуг) применяются дополнительные массивы V и W, где элементы vi и wj содержат значения весов для вершины vi и ребра (дуги) lj. Для неорграфов и мультиграфов MFO и FIпредставления совпадают.
Например, для орграфа на рис. 1,а массивы G и PMFO-представления графа имеют вид:
а для неорграфа на рис. 11,б:
5.2.6. Модифицированное FI-представление графа
(MFI-представление)
В отличие от MFO-представления графа в MFI-представлении указывается в массиве P верхние границы окончания списков вершин, смежных с заданной вершиной по входящим в нее дугам. Например, для орграфа на рис. 1,а MFI-представление графа имеет вид: , , а для неорграфа на рис. 11,б:
5.2.7. Сокращенные MFО и MFI-представления неорграфов
В целях экономии памяти обыкновенные графы можно представлять следующим образом: формируют массив FO, в котором сначала записывают номера вершин, смежных с первой вершиной, далее разделитель 0, затем номера вершин, смежных со второй вершиной и номера которых больше двух, а также разделитель 0 и т.д. Результатом является сокращенное FO-представление. Сокращенное MFO-представление получается заменой разделителей 0 на дополнительный массив Р, содержащий верхние границы списка номеров вершин, смежных с заданной вершиной, и больших, чем номер заданной вершины.
Например, для неорграфа на рис. 11,б сокращенное FO-представление имеет вид
