Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов

Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой 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].

Реализованная структура хранения позволяет быстро записать и считать данные из файла на жестком диске как в двоичном, так и в текстовом виде.

Похожие статьи




Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов

Предыдущая | Следующая