Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Представление и обработка данных в виде графов

Графы формально описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связыва­ющие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Графы могут быть ориентированы (подобно улицам с односторонним движением) или взвешены, когда каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные).

С формальной точки зрения граф представляет собой упорядоченную пару мно­жеств G = (V, Е), первое из которых состоит из вершин (узлов) графа, а второе — из его ребер. Ребро связывает между собой две вершины. При работе с графами часто решается вопрос, как проложить путь из ребер от одной вершины графа к другой. В этом случае говорят о движении по ребру, что означает переход из вершины А гра­фа в другую вершину В, связанную с ней ребром АВ (ребро графа, связывающее две вершины, для краткости обозначается этой парой вершин). В этом случае говорят, что ребро А примыкает к ребру В или что эти две вершины соседние.

Граф может быть ориентированным или нет. Ребра неориентированного гра­фа, чаще всего называемого просто графом, можно проходить в обоих направле­ниях (рис. 14.26). В этом случае ребро — это неупорядоченная пара вершин, его концов.

Рис. Неориентированный граф

 

В ориентированном графе, или орграфе, ребра представляют собой упорядочен­ные пары вершин: первая вершина — это начало ребра, вторая — его конец (рис.).

Полный граф — это граф, в котором каждая вершина соединена со всеми осталь­ными. Количество ребер в полном графе без петель с N вершинами равно (N2 - N)/2. В полном ориентированном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направ

Подграф (VS,Es) графа или орграфа (V,E) состоит из некоторого подмножества вершин, VsÌV,h некоторого подмножества ребер, их соединяющих, Es Ì Е.

Путь в графе или орграфе — это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины А в вершину В начина­ется в Л и проходит по набору ребер до тех пор, пока не будет достигнута вершина В. С формальной точки зрения путь из вершины Vx в вершину Vy — это последова­тельность ребер графа:

VxVx+1, Vx+1 Vx+2, ….. Vy-1 Vy

Необходимо, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина — количество ребер в нем. Длина пути АВ, ВС} CD, DE равна 4.

 

Рис. Ориентированный граф

 

Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл — это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется неукорененным деревом. Структура неукорененного дерева такая же, как и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем.

Рис. 14.28. Матрицы примыканий графа и орграфа

 

Информацию о графах или орграфах в пригодном для обработки компьютер­ными алгоритмами виде можно хранить двумя способами: в виде матрицы при­мыканий и в виде списка примыканий\

Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа, однако, если в графе мало ребер, эта матрица будет содержать гораздо боль­ше пустых клеток, чем заполненных. Длина списка примыканий пропорциональна числу ребер в графе, однако при пользовании списком время получения информа­ции о ребре увеличивается.

Матрица примыканий ConMat графа G = (V,E) с числом вершин | V| = N запи­сывается в виде двухмерного массива размером N х ЛГ. В каждой ячейке [у] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины Vi в вершину Vj ведет ребро, и тогда в ячейке записано значение 1:

Список примыканий ConList графа G = (V, Е) с числом вершин | V| = ЛГ записыва­ется в виде одномерного массива длины N, каждый элемент которого представляет собой ссылку на список. Такой список приписан каждой вершине графа и содержит по одному элементу на каждую вершину графа, соседнюю с данной.

На рис. 14.29 изображен список примыканий для орграфа, изображенного на рис. 14.27. На этом рисунке буквами LVN обозначены вершины графа, а буквами vN те вершины, к которым направлены выходящие из данной вершины ребра.

Рис. 14.29. Список примыканий для орграфа

При работе с графами часто приходится выполнять некоторое действие по од­ному разу с каждой из вершин графа, например, когда некоторую порцию инфор­мации следует передать каждому из компьютеров в сети. При этом нерационально посещать какой-либо компьютер дважды. Аналогичная ситуация возникает, если нужно собирать, а не распространять информацию.

Подобный обход можно совершать двумя способами. При обходе в глубину проход по выбранному пути осуществляется настолько глубоко, насколько это возможно, а при обходе по уровням происходит равномерное движение вдоль всех возможных направлений.

<== предыдущая лекция | следующая лекция ==>
Представление и обработка данных в виде деревьев | Обход по уровням
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 1517; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.