ДСо18-13-Заключение (Лекции Северов Часть 3), страница 3

Привлечение дополнительной памяти дляразмещения элементов с одинаковымпервичным индексом – область переполнения2. Размещение элементов с одинаковымипервичными индексами в незанятых ячейкахтого же массива – открытая адресация112Carnegie MellonГрафы113Основные понятияграф G = (V,E)V – множество вершин {A, B, C, D, …}Е – множество ребер {AB, BC, CD, …}¢ в полном графе любая пара вершин есть ребро¢ подграф G g=(v,e): v Í V и e Í EB¢ (не)направленость рёбер¢ число ненаправленных рёберполного графа с N вершинамиDравно N(N-1)/2¢AC114Структуры данных для представления графов¢Матрица смежностиA0ABCD¢B10C240D3560Список примыканийABBCDDCACADBDABC115Алгоритмы обхода¢¢В глубинуВ ширинуAADBDBFECFEC116Построение Минимального Остового ДереваОстовое дерево графа§ подграф из всех вершин и части рёбер§ связный§ ациклический¢ МОД взвешенного графа§ остовое дерево§ минимального суммарного веса¢ Трудоемкость полного перебора О(exp(N))¢ Жадный алгоритм¢§ на каждом шаге по части данных выберем лучший следующий117Алгоритм Прима роста МОДV = M È M’ È RM – уже найденные вершины МОД (дерево)M’ – вершины, смежные с вершинами М (кайма)R = V\M\M’ – остальные вершины графаУкоренить дерево (выбрать корень)¢ Окаймить корень¢ Пока кайма не опустеет¢§ Выбирать между деревом и каймой легчайшее ребро§ Дополнять дерево найденным ребром§ Уточнять кайму: вершины и рёбраотнесение к дереву – на диагонали матрицы смежности118Поиск кратчайших путей¢ищем не легчайшее, а элемент кратчайшего пути4A75C66D1FB2E8663G7119Алгоритм ДейкстрыV = M È M’ È RM – уже найденные вершины карты (дерево)M’ – вершины смежные с вершинами М (кайма)R = V\M\M’ – остальные вершины графа¢Начать карту§ выбрать начальную вершину дерева¢¢Окаймить началоПока нет конца§ Найти в кайме ближайшую к начальной§ Дополнить карту§ Уточнить кайму: вершины и рёбрарасстояние до начала – на диагонали матрицы смежности120ЦиклыЦикл – путь, где конец совпадает сначалом¢ В простом цикле различны всевершины, кроме начала и конца¢ Гамильтонов цикл прост исодержит все вершины графа¢ Эйлеров граф содержит цикл,проходящий через каждое ребрографа ровно один раз¢DBAC121Задача коммивояжера – найтигамильтонов циклAGBCDEFG1612136711A21188195B201315C14104D27E9FBFCED122Алгоритм поиска пути¢Пока не найден полный цикл§ Добавлять в путь ребро..1.2.3.легчайшеене третье при любой вершине путине образующее неполного циклаколичество рёбер пути при вершине – надиагонали матрицы смежности123Литература:Р.Седжвик «Алгоритмы на С++» -М.:«И.Д.

Вильямс», 2011. ISBN 978-5-8459-1650-1¢ Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн«Алгоритмы: построение и анализ» -М.:«И.Д. Вильямс», 2015. ISBN 5-8459-0857-4¢ Н.Вирт «Алгоритмы и структуры данных»-СПб.: Невский Диалект, 2001.ISBN 5-7940-0065-1¢124.