Определение всех компонент связности

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

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

3.4.

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

Еще по теме Определение всех компонент связности:

  1. Функциональные компоненты правового сознания.
  2. § 3.1. Основные структурные компоненты организации
  3. Участие образных компонентов в мышлении следователя
  4. 54. Основные компоненты социального контроля
  5. Основные компоненты.
  6. Дополнительные компоненты (общие).
  7. Дополнительные компоненты (специальные)
  8. Дополнительные компоненты общие.
  9. Дополнительные компоненты (общие).
  10. Дополнительные компоненты (специальные)
  11. Цель как компонент преступного действия