ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Операторы над ориентированными графамиНаиболее часто над ориентированными графами выполняются операторы: чтения меток вершин и дуг; вставки и удаления вершин и дуг; оператор перемещения по последовательностям дуг. В программах встречаются операторы, которые неформально можно описать подобно следующему оператору:
Для реализации такого оператора необходим индексный тип данных для работы с множеством вершин, смежных с заданной вершиной 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. Не нашли, что искали? Воспользуйтесь поиском:
|