Связность графа и обход графа

Итак, мы сформулировали некоторые фундаментальные понятия, относящиеся к графам. Пора перейти к одному из важнейших алгоритмических вопросов: связ- ности узлов. Допустим, имеется граф G = (V, E) и два конкретных узла 5 и t.
Нужно найти эффективный алгоритм для получения ответа на следующий вопрос: су- ществует ли в G путь из 5 в t? Будем называть его задачей проверки связности s—t.

Для очень малых графов бывает достаточно взглянуть на граф. Но для больших графов поиск пути может потребовать определенной работы. Более того, задача связности s-t также может рассматриваться как задача поиска пути в лабиринте. Если представить G как лабиринт, комнаты которого соответствуют узлам, а ко- ридоры — ребрам, соединяющим узлы (комнаты), то задача заключается в том, чтобы начать с комнаты 5 и добраться до другой заданной комнаты t. Несколько эффективный алгоритм можно разработать для этой задачи?

Рис. 3.2. На этом графе существуют пути от узла 1 к узлам 2-8, но не к узлам 9-13


В этом разделе описаны два естественных алгоритма для решения этой задачи на высоком уровне: поиск в ширину (BFS, Breadth-First Search) и поиск в глубину (DFS, Depth-First Search). В следующем разделе мы обсудим эффективную реа- лизацию обоих алгоритмов на основании структуры данных для представления графа, описывающего входные данные алгоритма.

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

Еще по теме Связность графа и обход графа:

  1. Почему надо обходиться без "надо"
  2. 1860
  3. ДИССОЦИАЦИЯ
  4. ПРОТИВОПОЛОЖHОСТИ В РАВЕHСТВАХ
  5. ТЕКСТ
  6. IV. 1. 2. Графы как средство описания систем.
  7. 1.11.8. Влияние фиксированных звёзд
  8. ПОХОЖИЙ СЛУЧАЙ
  9. СКОВАHАЯ ДУША
  10. Модус операнди
  11. РЕВ
  12. ИДЕНТИФИКАЦИЯ НАРЦИССИЧЕСКАЯ
  13. Журналистика эпохи реформ 60-х годов
  14. Ретроградный Юпитер в знаке Весов
  15. Защита права собственности: основания, способы, порядок
  16. 1.3.8. Влияние фиксированных звёзд
  17. Перемена лиц в обязательстве
  18. I. 2. 2. Специфика объектов психологии.