Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное приложение, которому в виде параметров командной строки можно передать необходимые для работы данные. Общий объем всех кодов с комментариями более 2500 строк и около 100 кбайт.
Представление графа в памяти ЭВМ
Для хранения данных о вершинах и ребрах графа в памяти ЭВМ был выбран списочный подход - для каждой вершины хранится число соседей и их номера. Как показали тесты, такой подход позволяет хранить данные о графах с числом вершин и ребер сотни миллионов, и ограничен только оперативной памятью ЭВМ. Данные хранятся в одном целочисленном массиве ig.
Таблица 1 - значения элементов массива ig представляющего граф в памяти ЭВМ
Ig[0] |
Размерность массива минус 1 |
Ig[1] |
Начало списка соседей вершины 1 - число вершин N плюс 2 |
Ig[2] |
Начало списка соседей вершины 2 |
Ig[N] |
Начало списка соседей вершины N |
Ig[N+1] |
Конец списка вершины N - размерность массива |
Ig[N+2] |
Соседи вершины 1 |
Ig[ig[2]-1] |
Соседи вершины 1 |
Ig[ig[2]] |
Соседи вершины 2 |
Ig[ig[3]-1] |
Соседи вершины 2 |
Ig[ig[3]] |
Соседи вершины 3 |
Ig[ig[N+1]-1] |
Соседи вершины N |
--- |
Элемента с номером ig[N+1] в массиве нет. |
Размерность массива составляет число вершин графа плюс удвоенное число ребер плюс два.
Для поиска соседей вершины i (1 <= i <= N) используется цикл for (j=ig[i]; j<ig[i+1]; j++) и номера соседей ig[j].
Число соседей вершины i (1 <= i <= N) составляет ig[i+1]-ig[i].
Реализованная структура хранения позволяет быстро записать и считать данные из файла на жестком диске как в двоичном, так и в текстовом виде.
Похожие статьи
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Входные параметры: входной файл, выходной файл, номер вершины, номер вершины. Если задаваемые номера вершин положительные, то добавляется соответствующее...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Алгоритма LBFS+ достаточно для трехмахового алгоритма распознавания единичных интервальных графов, но для случая интервальных графов необходимы...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
Работа алгоритма LBFS начинается с заданной вершины графа, которая в общем случае выбирается случайно. Получаемый порядок вершин также может быть основан...
-
Некоторые сведения из теории графов - Алгоритмы нескольких махов
Приведенные ниже определения взяты из [1,2,7-9], теоремы из [6]. Граф, или обыкновенный граф G -- это упорядоченная пара G := (V, E), где V -- это...
-
Исследования временных затрат алгоритмов - Алгоритмы нескольких махов
Исследования временных затрат алгоритмов были проведены для трех вариантов программ: LBFS4, LBFS3, MNS3; для двух вариантов сборки исполняемого файла:...
-
Численные эксперименты были проведены для следующих целей: Подтверждение корректности алгоритмов. Подтверждение линейности временных затрат алгоритмов. В...
-
Данный алгоритм (англ. Maximal Neighborhood Search - MNS) [7] в отличие от алгоритма BFS позволяет дополнительно упорядочить вершины в найденных...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
Формулировка задания: Составьте программу подсчета числа тех гласных букв в слове X, что не используются в написании слова Z. Описание входных/выходных и...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Оперативная память - Программное обеспечение персональных компьютеров
Обьем доступной оперативной памяти - один из важнейших параметров любого компьютера. Оперативная память или оперативное запоминающее устройство (ОЗУ или...
-
Для описания плана развития предприятия формируется: 1) Инвестиционный план Раздел "Инвестиционный план" предназначен для формирования календарного плана...
-
Кодирование информации -- процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи,...
-
ANSYS - универсальная программная система конечно-элементного (КЭ) анализа, которая на протяжении последних 30 лет является одним из мировых лидеров в...
-
Для того чтобы открыть папку, достаточно сделать по ее изображению двойной щелчок левой клавишей мыши. Можно также воспользоваться строкой "Открыть" в...
-
Цель Работы - использовать принципы архитектуры "Документ-Представление" для выборки и сохранения данных в файлах, а также взаимодействия элементов меню,...
-
ER - диаграмма базы данных была представлена на рис. 2. Рис.2. ER-диаграмма базы данных. Таблица admin - содержит два столбца login и password которые...
-
Цель Работы - изучить основные способы работы с пользовательским типом данных "класс", его объектами, методами и способы доступа к ним. - Теоретические...
-
Отчет представляет собой полученный на принтере выходной документ, предназначенный для конечного пользователя. Отчет - наилучшее средство для...
-
Розглянемо порядок заповнення інформації про внутрішньогосподарські пристрої земельних ділянок. Для всіх ділянок несільськогосподарського призначення...
-
Геоінформаційний система проектування моделювання Порядок реєстрації земельних ділянок З набранням чинності Законом України "Про Державний земельний...
-
Введение - Разработка программного средства, позволяющего оптимизировать SQL-скрипты
Актуальность. В настоящее время трудно найти фирму, которая не использовала бы базы данных в той или иной форме - учет сотрудников, клиентов, продаж....
-
1. Изучение теоретических аспектов использования: MS Word, MS Excel, MS Access, Paint и Photoshop... (ППО) Часть 1 : Руководство по выполнению...
-
Структура проекта Программа была реализована на языке Java в среде разработки AndroidStudio с помощью инструментов для разработки Android SDK. Разработка...
-
Цель Работы - научиться использовать элемент управления ListBox а также основные методы класса СListBox. Использование возможности контроля правильности...
-
Цель Работы - изучить приемы создания и использования шаблонов классов. - Теоретические сведения Достаточно часто встречаются классы, объекты которых...
-
Описание модулей системы Первый модуль - это перевод документов из формата pdf в формат txt. Как было представлено ранее, самым качественным ПО для...
-
Выбор интерфейса Пользовательский интерфейс представляет собой совокупность программных и аппаратных средств, обеспечивающих взаимодействие пользователя...
-
Расчет затрат, связанных с организацией рабочих мест для исполнителей проекта, проводится на основе требований СНИПа (санитарные нормы и правила) и...
-
Структура и интерфейс программы - Исследование алгоритмов
В этой части работы описывается процесс создания мобильного приложения на платформе Android, способного использовать обученные каскадные классификаторы...
-
Для написания АИС использовались следующие языки программирования, программные средства и библиотеки: - Язык программирования PHP 5.4; -...
-
В связи с увеличением числа сотрудников, работающих в компании, а также с расширением рабочего проекта, возникла проблема, связанная с версионностью...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
Разработка требований к программному модулю При разработке программного модуля следует опираться на требования и спецификации, определенные для...
-
Кодированием называется представление символов одного алфавита средствами другого алфавита. Алфавит содержащий два символа называется двоичным (часто их...
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов