Използване на обхождане на дълбочина за намиране на силно свързани компоненти

дълбочина

Силно свързани компоненти в графиката [math] G [/ math] могат да бъдат намерени чрез търсене с дълбочина първо в 3 стъпки:

  1. Изградете графика [math] H [/ math] със задни (обърнати) ръбове
  2. Извършете първо търсене по дълбочина в [math] H [/ math] и намерете [math] f [u] [/ math] - крайното време на обработка на върха [math] u [/ math]
  3. Извършете първо търсене в дълбочина в [math] G [/ math], итерирайки върховете във външния цикъл в низходящ ред [math] f [u] [/ math]

Дърветата за първо търсене в дълбочина, получени на третия етап, ще бъдат компонентите на силната свързаност на графиката [math] G [/ math] .
Тъй като силните свързани компоненти [math] G [/ math] и [math] H [/ math] на графиката са еднакви, първото търсене с дълбочина първо за намиране на [math] f [u] [/ math] може да бъде изпълнени на графиката [math] G [/ math], а втората на [math] H [/ math] .

Ако върховете [math] s [/ math] и [math] t [/ math] са били взаимно достъпни в графиката [math] G [/ math], то на третия етап ще бъде намерен път от един връх към друг, което означава, че в края на алгоритъма и двата върха лежат в едно и също поддърво.

  1. Върховете [math] s [/ math] и [math] t [/ math] лежат в едно и също DFS дърво на третия етап от алгоритъма. Това означава, че и двамата са достъпни от корена [math] r [/ math] на това дърво.
  2. Върхът [math] r [/ math] беше разгледан от второто обхождане на дълбочина по-рано от [math] s [/ math] и [math] t [/ math], което означава, че изходното време за първата дълбочина първото обръщане е по-голямо от изхода за време от върховете [math] s [/ math] и [math] t [/ math]. От това получаваме 2 случая:
    1. И двата върха бяха достижими от [math] r [/ math] в обърнатата графика. И това означава взаимна достижимост на върховете [math] s [/ math] и [math] r [/ math] и взаимната достижимост на върховете [math] r [/ math] и [math] t [/ math]. И добавяйки пътеките, получаваме взаимната достижимост на върховете [math] s [/ math] и [math] t [/ math] .
    2. Поне един не е достъпен от [math] r [/ math] в обърната графика, например [math] t [/ math]. Това означава, че [math] r [/ math] не е бил достъпен от [math] t [/ math] в обърнатата графика, тъй като времето за излизане на [math] r [/ math] е по-дълго. Това означава, че няма път между тези върхове, но последният не може да бъде, тъй като [math] t [/ math] е бил достъпен от [math] r [/ math] съгласно т. 1).