А. М. Горького математико-механический факультет кафедра алгебры и геометрии Библиотека структур данных и алгоритмов для графов и множеств Диплом СодержаниеДопустить к защите4. Структуры данных 75. Иерархия классов 157. Пример использования GRAPHLAB 25Краткий реферат1. Введение в проблему2. Общая характеристика системы GRAPHLAB3. Использование GRAPHLAB в разработках4. Структуры данных4.1. Скалярные структуры данных4.2. Списковые структуры данныхItem Head() - возвращает первый элемент списка; ItemItem Eject() - возвращает последний элемент, удаляя его из cписка; Inject(ItemОчередь (Queue) - это список, для которого разрешены лишь операции Head, Pop, Inject. ДекДек с ограниченным выводом4.3. Эффективные структуры данных4.3.1 Семейства непересекающихся множествЛевацкие хипыO(1); время на findmin O4.3.3 Бинарные деревья поиска4.3.4 Разрезание и связывание деревьевОриентированный граф (OrGraph).5. Иерархия классовПоиск Эйлерова цикла в графе6.2.1 Поиск Эйлерова циклаList& Euler(Graph&List& Euler(Graph&6.2.2 Поиск минимального остова (Алгоритм Краскала)6.2.3 Поиск минимального остова (Алгоритм крутящейся монетки)6.2.4. Кратчайший путь в бесконтурной сети6.3. Концепция решателей6.3.1 Поиск в глубинуList& Spisok() Возвращает список вершин графа в порядке обхода; VertexList& BackEdges() Возврашает список обратных ребер (не вошедших в остов); Vertex6.3.2 Поиск в ширину6.3.3 Топологическая сортировка6.3.4 Проверка графа на двудольность6.3.5 Поиск кратчайших путей в сетиNetwork* Tree() — возвращает дерево кратчайших путей в виде сети; List6.3.6 Поиск максимального потока в сети7. Пример использования GRAPHLABGraph G("in.glb"); // считываем граф G из файла in.glb предполагается, что in.glb в текущем каталоге// обработка List8. Особенности версии GRAPHLAB 3.009. Направления дальнейшего развитияПриложение 1. Заголовочные файлы.Приложение 2. Исходные тексты программ
