Главная Промышленная автоматика.

ГЛАВА 6

Ориентированные

графы

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

6.1. Основные определения

Ориентированный граф (или сокращенно орграф) G = (V, Е) состоит из множества верщин V и множества дуг Е. Верщины также называют узлами, а дуги - ориентированными ребрами. Дуга представима в виде упорядоченной пары верщин (v, и>), где верщина v называется началом, aw- концом дуги. Дугу (v, w) часто записывают как V W и изображают в виде

Говорят также, что дуга v -> w ведет от вершины v к вершине w, а верщина w смежная с верщиной i.

Пример 6.1. Парис. 6.1 показан орграф с четырьмя верщинами и пятью дугами. D


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

Верщины орграфа можно использовать для представления объектов, а дуги - для отнощений между объектами. Например, верщины орграфа могут представлять города, а дуги - марщруты рейсовых полетов самолетов из одного города в другой. В другом примере, рассмотренном нами ранее в разделе 4.2, в виде орграфа представлена блок-схема потока данных в компьютерной программе. В последнем примере верщины соответствуют блокам операторов программы, а дугам - направленное перемещение потоков данных.

Путем в орграфе называется последовательность верщин Vi, V2, г„, для которой существуют дуги Vi ~э Uj, - 13» in-i -> >n Этот путь начинается в верщине «1 и, проходя через верщины V2, v„-i, заканчивается в верщине Гп- Длина пу-



ти - количество дуг, составляющих путь, в данном случае длина пути равна л - 1. Как осрбый случай пути рассмотрим одну верщину v как путь длины О от верщины v к этой же верщине v. На рис. 6.1 последовательность верщин 1, 2, 4 образуют путь длины 2 от верщины 1 к верщине 4.

Нуть называется простым, если все верщины на нем, за исключением, может быть, первой и последней, различны. Цикл - это простой путь длины не менее 1, который начинается и заканчивается в одной и той же верщине. На рис. 6.1 верщины 3, 2, 4, 3 образуют цикл длины 3.

Во многих приложениях удобно к верщинам и дугам орграфа присоединить какую-либо информацию. Для этих целей используется помеченный орграф, т.е. орграф, у которого каждая дуга и/или каждая верщина имеет соответствующие метки. Меткой может быть имя, вес или стоимость (дуги), или значение данных какого-либо заданного типа.

Пример 6.2. На рис. 6.2 показан помеченный орграф, в котором каждая дуга имеет буквенную метку. Этот орграф имеет интересное свойство: любой цикл, начинающийся в верщине 1, порождает последовательность букв а и Ь, в которой всегда четное количество букв а и Ь. О


Рис. 6.2. Помеченный орграф

В помеченном орграфе верщина может иметь как имя, так и метку. Часто метки верщин мы будем использовать в качестве имен верщин. Так, на рис. 6.2 числа, помещенные в верщины, можно интерпретировать как имена верщин и как метки верщин.

6.2. Представления ориентированных графов

Для представления ориентированных графов можно использовать различные структуры данных. Выбор структуры данных зависит от операторов, которые будут применяться к верщинам и дугам орграфа. Одним из наиболее общих представлений орграфа G = (V, Е) является матрица смежности. Предположим, что множество верщин V= (1, 2, п). Матрица смежности для орграфа G - это матрица у1 размера я х я со значениями булевого типа, где A[i,j] = true тогда и только тогда, когда существует дуга из верщины / в верщину j. Часто в матрицах смежности значение true заменяется на 1, а значение false - на 0. Время доступа к элементам матрицы смежности зависит от размеров множества верщин и множества дуг. Представление орграфа в виде матрицы смежности удобно применять в тех алгоритмах, в которых надо часто проверять существование данной дуги.

Обобщением описанного представления орграфа с помощью матрицы смежности можно считать представление помеченного орграфа также посредством матрицы смежности, но у которой элемент Afi,JJ равен метке дуги / -> Если дуги от верщины i к верщине ; не существует, то значение АЦ, j] не может быть значением какой-либо допустимой метки, а может рассматриваться как "пустая" ячейка.

Пример 6.3. На рис. 6.3 показана матрица смежности для помеченного орграфа из рис. 6.2. Здесь дуги представлены меткой символьного типа, а пробел используется при отсутствии дуг. П



Основной недостаток матриц смежности заключается в том, что она требует Q(n) объема памяти, даже если дуг значительно меньше, чем п. Поэтому для чтения матрицы или нахождения в ней необходимого элемента требуется время порядка О(л), что не позволяет создавать алгоритмы с временем 0(п) для работы с орграфами, имеющими порядка 0(п) дуг.

Рис. 6.3. Матрица смежности для помеченного орграфа из рис. 6.2

Поэтому вместо матриц смежности часто используется другое представление для орграфа G = (V, Е), называемое представлением посредством списков смежности. Списком смежности для вершины г называется список всех вершин, смежных с вершиной i, причем определенным образом упорядоченный. Таким образом, орграф G можно представить посредством массива HEAD (Заголовок), чей элемент HEAD[i\ является указателем на список смежности вершины i. Представление орграфа с помощью списков смежности требует для хранения объем памяти, пропорциональный сумме количества вершин и количества дуг. Если количество дуг имеет порядок 0(п), то и общий объем необходимой памяти имеет такой же порядок. Но и для списков смежности время поиска определенной дуги может иметь порядок 0(п), так как такой же порядок может иметь количество дуг у определенной вершины.

Пример 6.4. На рис. 6.4 показана структура данных, представляющая орграф из рис. 6.1 посредством связанных списков смежности. Если дуги имеют метки, то их можно хранить в ячейках связанных списков.

9 \

2 1 1

* •

1 •

3 1 .

HEAD

Списки смежности

Рис. 6.4. Структура списков смежности для орг-Ьа из рис. 6.1

Для вставки и удаления элементов в списках смежности необходимо иметь массив HEAD, содержащий указатель на ячейки заголовков списков смежности, но не сами смежные вершины. Но если известно, что граф не будет подвергаться изменениям (или они будут незначительны), то предпочтительно сделать массив HEAD массивом курсоров на массив ADJ (от adjacency - смежность), где ячейки ADJ[HEAD[i}],ADJfHEADfiJ + 1] и т.д. содержат вершины, смежные с вершиной i, и эта последовательность смежных вершин заканчивается первым встреченным нулем в массиве ADJ. Пример такого представления для графа из рис. 6.1 показан на рис. 6.5. D

Здесь проявляется старая проблема языка Pascal: сложность выполнения вставки и удаления произвольных позиций в простых связанных списках.

6.2. ПРЕДСТАВЛЕНИЯ ОРИЕНТИГОВАННЬЕХ; ГРАФОВ





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 [57] 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0017