Связная компонента

Множество узлов, обнаруживаемых алгоритмом BFS, в точности соответствует множеству узлов, достижимых из начального узла 5. Это множество R называется компонентой связности G, содержащей s; зная компоненту связности, содержащую s, для ответа на вопрос о связности s-t достаточно проверить, принадлежит ли t компоненте связности.

Если задуматься, становится ясно, что BFS — всего лишь один из возможных способов построения этой компоненты. На более общем уровне компоненту R можно построить «проверкой» G в любом порядке, начиная c s. Сперва опреде- ляется R = {s}. Затем в любой момент времени, если удается найти ребро (u, v), для которого и R и v ⅜ R, узел v добавляется в R. В самом деле, если существует путь P из s в u, то существует путь из s в v, который состоит из P с последующим переходом по ребру (u, v). На рис. 3.4 изображен этот базовый шаг расширения компоненты R.

Рис. 3.4. При расширении компоненты связности, содержащей s, мы ищем узлы, которые еще не посещались, такие как v


Предположим, множество R продолжает расти до того момента, пока не оста- нется ни одного ребра, ведущего из R; иначе говоря, выполняется следующий алгоритм.

R состоит из узлов, к которым существует путь из s Перед началом выполнения R = {s}

Пока существует ребро (u, v), для которого u e 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, должно выполняться условие и R. Отсюда следует, что (u, v) — ребро, для которого и R и v ⅜ R; однако это

противоречит правилу остановки алгоритма. ■

Заметьте, что для любого узла t в компоненте R можно легко восстановить фак- тический путь от s к t по описанному выше принципу: для каждого узла v просто фиксируется ребро (u, v), которое рассматривалось на итерации, в которой узел v был добавлен в R. Перемещаясь по этим ребрам в обратном направлении от t, мы обрабатываем серию узлов, добавлявшихся на все более и более ранних итерациях, постепенно достигая s; таким образом определяется путь s-t.

В завершение следует отметить, что общий алгоритм расширения R недостаточ- но точно определен: как решить, какое ребро должно рассматриваться следующим? Среди прочего, алгоритм BFS предоставляет способ упорядочения посещаемых узлов — по последовательным уровням, на основании их расстояния от s. Однако существуют и другие естественные способы расширения компоненты, часть из которых ведет к эффективным алгоритмам решения задачи связности с приме- нением поисковых схем, основанных на других структурах. Сейчас мы займемся другим алгоритмом такого рода — поиском в глубину — и изучим некоторые из его базовых свойств.

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

Еще по теме Связная компонента:

  1. Функциональные компоненты правового сознания.
  2. § 3.1. Основные структурные компоненты организации
  3. Участие образных компонентов в мышлении следователя
  4. Основные компоненты.
  5. 54. Основные компоненты социального контроля
  6. Дополнительные компоненты (общие).
  7. Дополнительные компоненты (специальные)
  8. Дополнительные компоненты общие.
  9. Дополнительные компоненты (общие).
  10. Дополнительные компоненты (специальные)
  11. Модуляционные компоненты психологии личности
  12. Модуляционные компоненты психологии личности
  13. Кроме содержания, преступное действие имеет внутреннюю структуру, главными компонентами которой являются:
  14. Цель как компонент преступного действия
  15. 3. 3. ЭМОЦИОНАЛЬНЫЕ КОМПОНЕНТЫ ТЕРАПЕВТИЧЕСКОГО КЛИМАТА. СОЗДАНИЕ ОБОЮДНОГО ДОВЕРИЯ
  16. 4.2. Научная эрудиция, ценностные ориентации как компоненты педагогической культуры
  17. Алистэр Коуберн. Люди как нелинейные и наиболее важные компоненты в создании программного обеспечения, 1999
  18. Риторические вопросы не содержат необходимого вопросительного компонента и тем самым вызывают у собеседника пассивную реакцию.
  19. 3. 2. ТЕРАПЕВТИЧЕСКИЙ КЛИМАТ. ФИЗИЧЕСКИЕ КОМПОНЕНТЫ ТЕРАПЕВТИЧЕСКОГО КЛИМАТА