Список дуг

1.8.3. Список дуг.

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

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

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

Список дуг

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

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

Список дуг

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