8 Алгоритмы на графах

8.1 Машинное представление графов

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

Будем рассматривать как ориентированные графы, так и неориентированные. Будем обозначать граф G=<V,E>, где V - множество вершин, а Е - множество ребер, причем Е с: V х V - для ориентированного графа

и

Е с: {{х, у}:х,у е V л х Ф у) - для неориентированного графа.

Будем использовать также обозначения | V \ = п, | Е \ = m (мощность множества).

В теории графов классическим способом представления графа является матрица инциденций. Это матрица А с п строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентирован­ного графа столбец, соответствующий дуге (х,у)еЕ, содержит +1 в строке, соответствующей вершине х, -1 в строке, соответствующей вершине у и нули во всех остальных строках. Петлю, т.е. дугу вида (х, х), удобно представлять другим значением, например 2, в строке х.

Для неориентированного графа столбец, соответствующий ребру {х, у}, содержит 1 в строках, соответст­вующих х и у, и 0 - во всех остальных строках (рис. 28, рис. 29).

5

а)

1

" ©

п= 6,m = 7

©	©	©	© © © ©
Г1	1	0	00 00
-1	0	-1	0 0 0 0
0	-1	1	10 0 0

6

3

0 0 0-1-10 о 0 0 0 0 11-1 0 0 0 0 0-11 (1,2) (1,3) (3,2) (3,4) (5,4) (5,6) (6,5) Рис. 28 Матрица инциденций для ориентированного графа

1

б)

п = 6, m = 9

3 ©

A

ф ©©© ©©© ®@ 1110 0 0 0 0 0"

1	0	0	1	1 00	0	0
0	1	0	1	01 0	0	0
0	0	0	0	0 11	1	0
0	0	1	0	10 1	0	1

0000000 11

{1,2} {1,5} {2,5} {4,5} {5,6} {1,3} {2,3} {3,4} {4,6}

Рис. 29 Матрица инциденций для неориентированного графа

С алгоритмической точки зрения матрица инциденций является одним из самых худших способов пред­ставления графа, так как:

• требуется n х m ячеек памяти, причем большинство ячеек занято нулями;

• неудобен доступ к информации, т.к. ответ на вопросы: существует ли дуга (х, у)? к каким вершинам ве­дут ребра из х? - требует в худшем случае перебора всех столбцов, т.е. m шагов.

Немного лучше способ представления графа с помощью матрицы смежности B

размера n x m, где

ij

b_ij = 1, если существует ребро, ведущее из x в y, и b_ij = 0 – противном случае. При этом подразумевается, что

0 110 0 0

000 000

0 10 10 0

000 000

0 0 0 10 1

0 0 0 0 10

1 2 3 4 5 6

а)

В

ребро {x, y} неориентированного графа идет как от x к y, так и от y к x. Поэтому матрица смежности для неори­ентированного графа всегда симметрична. Для наших графов матрицы смежности имеют вид:

1	б) 1	0	1	1	0	1	0
2	2	1 1	0	1	0	1	0
3	3		1	0	1	0	0
4	4	0	0	1	0	1	1
5	5	1	1	0	1	0	1
6	6	_о	0	0	1	1	0
		1	2	3	4	5	6

Основное преимущество матрицы смежности состоит в том, что за один шаг можно ответить на вопрос – существует ли ребро из x в y?

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

Более экономным в отношении памяти (особенно для неплотных графов, когда m гораздо меньше n² ) яв­ляется способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (x, y) соответст­вует дуге (x, y), если граф ориентированный, и ребру {x, y}, если граф неориентированный. В нашем случае списки пар:

а)

12	б)	12
13		1 3
32		1 5
34		2 3
54		2 5
56		3 4
63 ,		4 5 46 56

Очевидно, что в этом случае объем памяти составляет 2т. Неудобством является большое число шагов (порядка m в худшем случае) для нахождения множества вершин, к которым ведут ребра из данной вершины.

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

Лучшим решением во многих случаях является структура данных, которую назовем списками инцидент­ности. Она содержит для каждой вершины V е V список вершин и таких, что V —> и для ориентированного графа и V — и для неориентированного графа. Каждый элемент такого списка является записью г, состоящей из двух полей:

г.строка - вершина графа;

г.след - указатель на следующую запись в списке.

Для последней записи в списке - г.след = nil. Указатель на начало каждого списка хранится в таблице НАЧАЛО. Таким образом НАЧАЛО[v] - указатель на начало списка, содержащего вершины из множества {u: (v, и)} для ориентированного графа или {u: {v, и}} для неориентированного графа, соответственно.

Весь список обозначим (неформально) СПИСОК[у], а цикл, выполняющий некоторую операцию над каж­дым элементом и из этого списка, запишем как

for ueСПИСОК[v] do ...

Отметим, что для неориентированного графа каждое ребро {и, v} представлено дважды:

через вершину v в списке СПИСОК[и] и

через вершину и в списке СПИСОК[у].

Для наших примеров список инцидентности СПИСОК[у], ve V выглядят следующим образом:

а) НАЧАЛО

б) НАЧАЛО

1		^2 | —^3 |Nii
I	Nil
3		.2 £ГШ
4	Nil
5		H4 1 H6 M
	—^=rl^5 |ш

1

2

3

4

5

6

	—i21	^3 |^s \m
	—\^x	— з —|ГШ
	—\^x 1	^2 | —^4 |Nil
	—\^ъ1	•|5 |—Цб |ш
	. i —|T	—-41H6 и
	—"i41	^ |Nii

Во многих алгоритмах структура графа динамически модифицируется добавлением и удалением ребер. В таких случаях полагаем, что в списке СПИСОК[u] элемент, содержащий вершину v, снабжен указателем на элемент списка СПИСОК[v], содержащий вершину u, что каждый элемент списка снабжен указателем не толь­ко на последующий, но и на предыдущий элемент. Тогда удаляя некоторый элемент из списка, мы можем легко за ограниченное число шагов удалить и другой элемент, представляющий то же самое ребро, не просматривая список, содержащий этот элемент.

Число ячеек памяти, необходимых для представления графа с помощью списков инцидентности, имеет порядок (n + m).

оператор P для всех элементов x X в произвольной последовательно-

FOR x∈X DO P

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

СТЕК <= x x <= СТЕК

ОЧЕРЕДЬ x

x <= ОЧЕРЕДЬ

выполнять множества сти;

<=

поместить значение переменной х в стек; считать элемент из вершины стека и принять его за значение переменной х;

включить элемент х в очередь в качестве по­следнего элемента;

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

Для любого алгоритма нас будет интересовать его вычислительная сложность, т.е. число шагов, выпол­няемых в худшем случае, как функция от размерности задачи. Под размерностью задачи будем понимать |V| или пару <|V|, |Е|>. Тогда сложность алгоритма будет fin) - наибольшее число шагов алгоритма для произволь­ного графа с п вершинами илиДп, т) - наибольшее число шагов алгоритма для произвольного графа с п вер­шинами и m ребрами. При этом под шагом, вообще говоря, следует понимать любую машинную команду (пе­ренос слова из памяти в буфер и наоборот, выполнение арифметических операций, условные переходы, ввод-вывод, косвенную адресацию и т.д.). Однако нас будет интересовать не точная сложность в этом смысле, а так называемая асимптотическая сложность, т.е. скорость увеличения числа шагов алгоритма при неограниченном (теоретически) росте размерности задачи. Тогда для характеристики сложности удобно использовать такие обозначения:

f(n) 0(g(n))

f(n) fXg(n))

<=>

существуют константы С, N такие, что f(n)<C g(n) для любого n>N

<=>

g(n) - некоторая заданная функция существуют константы С, N такие, что f(n) >С g(n) для любого n>N Читается: 0(g(n)) - "порядка не более чем g(n)"

Q(g(n)) - "порядка не менее чем g(n)" То же для функции/п, т).