Реализация перебора графа с использованием очередей и стеков

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

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

Еще по теме Реализация перебора графа с использованием очередей и стеков:

  1. ПОИСК СВОЕЙ ЖИЗНИ ПЕРЕБОРОМ
  2. Наряды вне очереди
  3. Раздел III Использование достижений криминалистической психологии при собирании, оценке, использовании личностной информации
  4. 2. Наследники иных (последующих) очередей
  5. 1. Наследники первой очереди
  6. Статья 1263. Третья очередь наследников по закону
  7. Статья 1264. Четвертая очередь наследников по закону
  8. Статья 1265. Пятая очередь наследников по закону
  9. Статья 1262. Вторая очередь наследников по закону
  10. Статья 1261. Первая очередь наследников по закону
  11. Мудрец, в первую очередь, – гармоничный человек
  12. Статья 231. Незаконный сбор с целью использования или использование сведений, составляющих коммерческую или банковскую тайну
  13. Если мы спешим, то в универсаме становимся в очередь, которая движется медленнее всех остальных.
  14. 4.2. Реализация
  15. Глава 6. Реализация права
  16. 4. Реализация прав по ипотеке
  17. 3.3. Дальнейшая реализация проекта