Связность графа и обход графа
Для очень малых графов бывает достаточно взглянуть на граф. Но для больших графов поиск пути может потребовать определенной работы. Более того, задача связности s-t также может рассматриваться как задача поиска пути в лабиринте. Если представить G как лабиринт, комнаты которого соответствуют узлам, а ко- ридоры — ребрам, соединяющим узлы (комнаты), то задача заключается в том, чтобы начать с комнаты 5 и добраться до другой заданной комнаты t. Несколько эффективный алгоритм можно разработать для этой задачи?
Рис. 3.2. На этом графе существуют пути от узла 1 к узлам 2-8, но не к узлам 9-13 |
В этом разделе описаны два естественных алгоритма для решения этой задачи на высоком уровне: поиск в ширину (BFS, Breadth-First Search) и поиск в глубину (DFS, Depth-First Search). В следующем разделе мы обсудим эффективную реа- лизацию обоих алгоритмов на основании структуры данных для представления графа, описывающего входные данные алгоритма.
Еще по теме Связность графа и обход графа:
- Почему надо обходиться без "надо"
- 1860
- ДИССОЦИАЦИЯ
- ПРОТИВОПОЛОЖHОСТИ В РАВЕHСТВАХ
- ТЕКСТ
- IV. 1. 2. Графы как средство описания систем.
- 1.11.8. Влияние фиксированных звёзд
- ПОХОЖИЙ СЛУЧАЙ
- СКОВАHАЯ ДУША
- Модус операнди
- РЕВ
- ИДЕНТИФИКАЦИЯ НАРЦИССИЧЕСКАЯ
- Журналистика эпохи реформ 60-х годов
- Ретроградный Юпитер в знаке Весов
- Защита права собственности: основания, способы, порядок
- 1.3.8. Влияние фиксированных звёзд
- Перемена лиц в обязательстве
- I. 2. 2. Специфика объектов психологии.