Представление направленных графов

Для представления направленных графов в контексте проектирования алгоритмов используется разновидность представления списка смежности, использовавшегося для ненаправленных графов. Вместо одного списка соседей в каждом узле хра- нятся два списка: один состоит из узлов, к которым ведут ребра от данного узла, а второй — из узлов, из которых выходят ребра к данному узлу.
Таким образом, алгоритм, просматривающий узел и, может получить информацию как об узлах, достижимых при переходе на один шаг вперед по направленному ребру, так и об узлах, которые были бы достижимы при возврате на один шаг в обратном направ- лении (по ребру, ведущему к и).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Представление направленных графов:

  1. ПРЕДСТАВЛЕНИЕ
  2. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  3. Музыкальное представление на телевидении
  4. ПРЕДСТАВЛЕНИЕ ВЫТЕСНЕННОЕ
  5. КОНЦЕПЦИЯ ПРЕДСТАВЛЕНИЙ СОЦИАЛЬНЫХ
  6. ПРЕДСТАВЛЕНИЕ ОБЩЕЕ
  7. ПРЕДСТАВЛЕНИЕ ПРОСТРАНСТВЕННОЕ
  8. Представления о деньгах
  9. 2.4.2. Наглядное представление оригинальной ситуации
  10. ПРЕДСТАВЛЕНИЕ РЕЛИГИОЗНОЕ: ПРОИСХОЖДЕНИЕ
  11. § 8.1. Общее представление о конфликтах в организации
  12. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ