- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
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 ©
ф ©©© ©©© ®@ 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
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
а)
В
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?
Недостатком является тот факт, что независимо от числа ребер объем занимаемой памяти составляет n2 . На практике это неудобство иногда можно исправить, храня целую строку или столбец в одном машинном слове (для малых n).
Более экономным в отношении памяти (особенно для неплотных графов, когда m гораздо меньше n2 ) является способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (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)" То же для функции/п, т).