Список дуг

Для этого способа хранения структуры составляется таблица, каждая строка в которой фиксирует дугу графа следования, причем в первом элементе строки записывается обозначение начальной вершины дуги, а во втором элементе - обозначение конечной вершины дуги. Если таблица будет представлена в памяти ЭВМ как массив размерностью 2 x k, где k - количество дуг, то массив будет занимать объем

V=2k слов


Рассмотрим пример структуры сборочного технологического процесса.

Список дуг для этой структуры приведен ниже

Список дуг
Оi
Oj
O1
O2
O3
O2
O2
O5
O4
O5


Для этого примера V=8 слов. Этот способ всегда лучше, чем первые два способа в случае, когда структура представляет собой либо линейный граф, либо граф типа "дерево". Для структуры типа "сеть" хранение в виде списка дуг выгоднее, если k < 1.5n. Ниже приведена структура операции типа "сеть".

При хранении этой структуры списком дуг - V=20 слов.

Список дуг
pi
pj
p1
p2
p2
p3
p2
p4
p2
p5
p2
p6
p3
p7
p4
p7
p5
p7
p6
p7
p7
p8


Изменение списка дуг производится путем добавления или вычеркивания строк.