Набор всех компонент связности
До настоящего момента мы говорили о компоненте связности, содержащей кон- кретный узел s. Однако для каждого узла в графе существует своя компонента связности. Какими отношениями связаны эти компоненты?
Как выясняется, эти отношения четко структурированы и описываются следу- ющим утверждением.
(3.8) Для любых двух узлов s и t в графе их компоненты связности либо идентичны, либо не пересекаются.
Доказательство. Возьмем любые два узла s и t в графе G, между которыми существует путь. Утверждается, что компоненты связности, содержащие s и t, представляют собой одно и то же множество.
Действительно, для любого узла v в компоненте s узел v также должен быть достижим из t через путь: мы можем про- сто перейти из t в s, а затем из s в v. Аналогичные рассуждения работают при смене ролей s и t, так что узел входит в компоненту одного в том, и только том случае, если он также входит в компоненту другого.
С другой стороны, если пути между s и t не существует, не может быть узла v, вхо- дящего в компоненту связности каждого из них. Если бы такой узел v существовал, то мы могли бы перейти от s к v, а затем к t, строя путь между s и t. Следовательно, если пути между s и t не существует, то их компоненты связности изолированы.
Из этого доказательства вытекает естественный алгоритм получения всех ком- понент связности графа, основанный на расширении одной компоненты за раз. Алгоритм начинает с произвольного узла s, а затем использует BFS (или DFS) для генерирования его компоненты связности.
Далее мы находим узел v (если он существует), который не был посещен при поиске от s, и итеративным методом, используя BFS от узла v, генерирует компоненту связности — которая, согласно (3.8), изолирована от компоненты s. Это продолжается до тех пор, пока алгоритм не посетит все узлы.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу