Алгоритмы и структуры данных

Здесь построение MST начинается с графа, состоящего только из n вершин графа G и не имеющего ребер. Таким образом, каждая вершина является связанной (сама с собой) компонентой. Это дает n связанных компонентов. В процессе выполнения алгоритма связанные компоненты постепенно объединяются друг с другом, формируя остовное дерево (рис. 59).

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

 

привести к образованию цикла. Число ребер, необходимое для ос-товного дерева равно n-1. Граф связан, а значит E содержит как минимум такое их количество. Когда остовное дерево будет содержать n-1 ребер, алгоритм завершается:

Создать список ребер L,  в неубывающем по длине порядке while число отмеченных ребер < n-1 do begin Удалить w из головы списка L;

if w соединяет две несвязанных компоненты then

отметить w и добавить к MST 
else {w - внутри компоненты}

не отмечать w {это приведет к циклу в MST}

end;

Сложность алгоритма для графа с n вершинами и m ребрами пропорциональна O(mlog m).

Библиографический список

1. *Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2001. 384 с.

3. *Бентли Д. Жемчужины творчества программистов. М.: Радио и

связь, 1990.

4. *Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир,

1985.

5. *Вирт Н. Алгоритмы и структуры данных. М: Мир, 1989. 360 с.

6. *Грин Д., Кнут Д. Математические методы анализа алгоритмов. М: Мир, 1987.
7. *Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

8. *Дейкстра Э. Дисциплина программирования. М: Мир, 1978.

9. *Кнут Д. Е. Искусство программирования для ЭВМ: В 3 т. М.:

Мир, 1976.

10. Кнут Д. Е. Искусство программирования: В 3 т. М.: Вильямс,

2000.

11. *Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.
12. Лэгсам Й., Огенстайн М. Структуры данных для персональных ЭВМ. М.: Мир, 1989. 586 с.
13. *Структуры и алгоритмы обработки данных/ В. А. Матьяш, В. А. Путилов, В. В. Фильчаков, С. В. Щекин. Апатиты: КФ ПетрГУ,

2000. 80 с.

14. *Оре О. Графы и их применение. М.: Мир, 1965.
15. *Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.
16. *Сибуя М., Ямамото Т. Алгоритмы обработки данных. М.: Мир,

1986. 218 с.

17. *Успенский В. А., Семенов А. Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987.
18. *Харари Ф. Теория графов. М.: Мир, 1973.

Русскоязычные ресурсы Internet

1. http://algo.4u.ru/
2. http://algolist.manual.ru/
3. http://alglib.chat.ru/
4. http://algo.do.ru/
5. http://hcinsu.chat.ru/
6. http://algolist.da.ru/
7. http://progstone.narod.ru/links/wantalgo.html
8. http://www.sevmashvtuz.edu/links/algorithms.html

ОГЛАВЛЕНИЕ

Предисловие  3

ВВЕДЕНИЕ  4

Понятия алгоритма и структуры данных  4

Анализ сложности и эффективности алгоритмов и структур данных  7

1. СТРУКТУРЫ ДАННЫХ  11

1.1. Элементарные данные  11

1.1.1. Данные числовых типов  11

1. Данные целочисленного типа  11
2. Данные вещественного типа  12
3. Операции над данными числовых типов  12

 

2. Данные символьного типа  13
3. Данные логического типа   1 4
4. Данные типа указатель   1 4

1.2. Линейные структуры данных  16

1. Массив  16
2. Строка  1 7
3. Запись  18
4. Множество  19
5. Таблица  20
6. Линейные списки   21

 

1. Линейный однонаправленный список  22
2. Линейный двунаправленный список  27

1.2.7. Циклические списки  3 0

1. Циклический однонаправленный список  30
2. Циклический двунаправленный список  34

1.2.8. Разреженные матрицы  37

1. Матрицы с математическим описанием местоположения элементов  37

2. Матрицы со случайным расположением элементов 3 8

1.2.9. Стек  41

10. Очередь  43
11. Дек   46

1.3. Нелинейные структуры данных  49

1. Мультисписки   49
2. Слоеные списки   50
3. Графы  51

 

1. Спецификация  51
2. Реализация  52

1.3.4. Деревья   55

1. Общие понятия  55
2. Обходы деревьев  57
3. Спецификация двоичных деревьев  58
4. Реализация  59
5. Основные операции  61

1.4. Файлы  62

1. Организация  6 4
2. B-деревья  67

 

1. Представление файлов B-деревьями  67
2. Основные операции   69
3. Общая оценка B-деревьев  76

2. АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ  7 8

1. NP-сложные и труднорешаемые задачи  78
2. Методы разработки алгоритмов  79

 

1. Метод декомпозиции  79
2. Динамическое программирование  81
3. Поиск с возвратом  82
4. Метод ветвей и границ  85
5. Метод альфа-бета отсечения  86
6. Локальные и глобальные оптимальные решения   8 7

2.3. Алгоритмы поиска  8 9

2.3.1. Поиск в линейных структурах  8 9

1. Последовательный (линейный) поиск  89
2. Бинарный поиск  91

2.3.2. Хеширование данных   92

1. Функция хеширования  92
2. Открытое хеширование  95
3. Закрытое хеширование  98
4. Реструктуризация хеш-таблиц  103

2.3.4. Поиск по вторичным ключам  104

1. Инвертированные индексы  104
2. Битовые карты   105

2.3.4. Использование деревьев в задачах поиска   106

1. Упорядоченные деревья поиска  106
2. Случайные деревья поиска   111
3. Оптимальные деревья поиска   112
4. Сбалансированные по высоте деревья поиска   113

2.3.5. Поиск в тексте   118

1. Прямой поиск   118
2. Алгоритм Кнута, Мориса и Пратта  120
3. Алгоритм Боуера и Мура  123

2.4. Алгоритмы кодирования (сжатия) данных  12 5

1. Основные виды сжатия   125
2. Метод Хаффмана. Оптимальные префиксные коды   126
3. Кодовые деревья  127

2.5. Алгоритмы сортировки  13 0

1. Основные виды сортировки  130
2. Алгоритмы внутренней сортировки  131

 

1. Сортировка подсчетом  131
2. Сортировка простым включением  132
3. Сортировка методом Шелла  134
4. Сортировка простым извлечением  136
5. Древесная сортировка   137
6. Сортировка методом пузырька   140
7. Быстрая сортировка (Хоара)  141
8. Сортировка слиянием   145
9. Сортировка распределением  147

2.5.2.10. Сравнение алгоритмов внутренней сортировки... 150

2.5.3. Алгоритмы внешней сортировки  15 2

2.6. Алгоритмы на графах   153

1. Алгоритм определения циклов  153
2. Алгоритмы обхода графа   1 54

 

1. Поиск в глубину  155
2. Поиск в ширину (волновой алгоритм)  156

2.6.3. Нахождение кратчайшего пути  1 58

1. Алгоритм Дейкстры   158
2. Алгоритм Флойда  159
3. Переборные алгоритмы  161

2.6.4. Нахождение минимального остовного дерева   164

1. Алгоритм Прима   164
2. Алгоритм Крускала  165

Библиографический список  167

Приложение. Русскоязычные ресурсы Internet   168

 

 

Рис. 15. Обходы деревьев

Рис. 15. Обходы деревьев

Рис. 17. Двоичное дерево и его организация