Связная компонента
Множество узлов, обнаруживаемых алгоритмом BFS, в точности соответствует множеству узлов, достижимых из начального узла s. Это множество R называется компонентой связности G, содержащей s; зная компоненту связности, содержащую s, для ответа на вопрос о связности s–t достаточно проверить, принадлежит ли t компоненте связности.
Если задуматься, становится ясно, что BFS — всего лишь один из возможных способов построения этой компоненты. На более общем уровне компоненту R можно построить «проверкой» G в любом порядке, начиная c s.
Предположим, множество R продолжает расти до того момента, пока не оста- нется ни одного ребра, ведущего из R; иначе говоря, выполняется следующий алгоритм.
R состоит из узлов, к которым существует путь из s
Перед началом выполнения R = {s}
Пока существует ребро (u, v), для которого u Ѯ R и v ѯ R
Добавить v в R
Конец Пока
Ниже сформулировано ключевое свойство этого алгоритма.
(3.5) Множество R, построенное в конце выполнения этого алгоритма, в точ- ности совпадает с компонентой связности G, содержащей s.
Доказательство. Ранее уже было показано, что для любого узла v Ѯ R суще- ствует путь из s в v.
Теперь рассмотрим узел w Ѯ R; действуя от обратного, предположим, что в G существует путь s–w, который будет обозначаться P. Так как s Ѯ R, но w ѯ R, в пути P должен существовать первый узел v, который не принадлежит R, и этот узел v отличен от s.
Следовательно, должен существовать узел u, непосредственно предшествующий v в P, такой что (u, v) является ребром. Более того, поскольку v является первым узлом P, не принадлежащим R, должно выполняться условие u Ѯ R. Отсюда следует, что (u, v) — ребро, для которого u Ѯ R и v ѯ R; однако это противоречит правилу остановки алгоритма.
Заметьте, что для любого узла t в компоненте R можно легко восстановить фак- тический путь от s к t по описанному выше принципу: для каждого узла v просто фиксируется ребро (u, v), которое рассматривалось на итерации, в которой узел v был добавлен в R. Перемещаясь по этим ребрам в обратном направлении от t, мы обрабатываем серию узлов, добавлявшихся на все более и более ранних итерациях, постепенно достигая s; таким образом определяется путь s–t.
В завершение следует отметить, что общий алгоритм расширения R недостаточ- но точно определен: как решить, какое ребро должно рассматриваться следующим? Среди прочего, алгоритм BFS предоставляет способ упорядочения посещаемых узлов — по последовательным уровням, на основании их расстояния от s.
Однако существуют и другие естественные способы расширения компоненты, часть из которых ведет к эффективным алгоритмам решения задачи связности с приме- нением поисковых схем, основанных на других структурах. Сейчас мы займемся другим алгоритмом такого рода — поиском в глубину — и изучим некоторые из его базовых свойств.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу