Определение всех компонент связности
Хотя ранее время выполнения BFS и DFS выражалось в виде O(m + n), где m и n — общее количество ребер и узлов в графе, фактически оба вида поиска — и BFS и DFS — работают только с ребрами и узлами компоненты связности, со- держащей начальный узел. (Другие ребра и узлы им не видны.) Таким образом, приведенный выше алгоритм, хотя он и может выполнять BFS и DFS несколько раз, выполняет постоянный объем работы для каждого конкретного узла или ребра в итерации для той компоненты связности, которой этот узел или ребро принадлежит. А следовательно, общее время выполнения алгоритма по-прежнему остается равным O(m + n).
3.4.
Источник:
Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016
Еще по теме Определение всех компонент связности:
- Функциональные компоненты правового сознания.
- § 3.1. Основные структурные компоненты организации
- Участие образных компонентов в мышлении следователя
- 54. Основные компоненты социального контроля
- Основные компоненты.
- Дополнительные компоненты (общие).
- Дополнительные компоненты (специальные)
- Дополнительные компоненты общие.
- Дополнительные компоненты (общие).
- Дополнительные компоненты (специальные)
- Цель как компонент преступного действия
-
Windows -
Архитектура компьютера -
Интернет -
Информатика -
Компьютер -
Компьютерные и телекоммуникационные системы -
Программирование -
Социальные сети -
-
Английский язык -
Астрология -
Астрономия -
Биология -
Военная литература -
Журналистика -
Компьютерная инженерия -
Педагогика -
Право -
Психология -
Социология -
Lecture.Center