Операторы над ориентированными графами

Наиболее часто над ориентированными графами выполняются операторы: чтения меток вершин и дуг; вставки и удаления вершин и дуг; оператор перемещения по последовательностям дуг.

В программах встречаются операторы, которые неформально можно описать подобно следующему оператору:

Для реализации такого оператора необходим индексный тип данных для работы с множеством вершин, смежных с заданной вершиной v. Например, если для представления орграфа используются списки смежности, то индекс – это позиция в списке смежности вершины v. Если применяется матрица смежности, тогда индекс – целое число, соответствующее смежной вершине. Для просмотра множества смежных вершин необходимы следующие три оператора.

1. FIRST(v) возвращает индекс первой вершины, смежной с вершиной v. Если v не имеет смежных вершин, то возвращается «нулевая» вершина

2. NEXT(v, i) возвращает индекс вершины, смежной с v, следующий за индексом i. Если I – это индекс последней вершины, смежной с вершиной v, то возвращается

3. VERTEX(v, i) возвращает вершину с индексом I из множества вершин, смежных с v.

Если для представления орграфа используется матрица смежности, то функция VERTEX(v, i) просто возвращает индекс i. Ниже приведен код функций FIRST(v) и NEXT(v, i). В этом листинге матрица смежности А размера n n определена вне этих функций с помощью следующего объявления:

Последовательный просмотр вершин, смежных с вершиной v.

Дата добавления: 2015-07-16