Силно-свързани компоненти

Strongly Connected Components

В тази тема ще разгледаме какво са силно-свързаните компоненти (и как се различават от свързани компоненти), един лесен алгоритъм, с който да ги намираме (алгоритъмът на Косаражу), и в какви задачи ще ни трябват те.
Автор: Александър Георгиев

Свързани компоненти

!Забележете, че това е различно от клика, където между всеки два върха трябва да има ребро.
Свързана компонента (или просто компонента) наричаме максимално подмножество от върхове в ненасочен граф, между всеки два от които има път. Тоест, от всеки връх в компонентата можем да стигнем до всеки друг, ползвайки едно или повече ребра, като в същото време няма връх, до който да можем да стигнем и да не е в компонентата (последното е изискването за максималност).

Пример за свързани компоненти

Например, представете си картата на света с нейните градове и пътища, по които могат да преминават коли. Градовете в Европа, Азия и Африка образуват една свързана компонента, тъй като от всеки от тях може да се стигне до всеки друг по пътната мрежа. Африка, сама по себе си, не образува свързана компонента, тъй като можем да стигнем по пътищата до Азия, тоест изискването за максималност не е изпълнено.

Градовете в Австралия образуват друга компонента. Тези в Южна и Северна Америка образуват трета компонента (забележете, че от северна може да се стигне до южна с кола). Всеки остров, който не е свързан с мост до континент или до други острови, също сам по себе си е свързана компонента (стига да има поне един град (връх в графа) на острова, разбира се).

В следния пример сме показали граф с три свързани компоненти:
TODO

Намиране на свързани компоненти

Тъй като нямаме наложени ограничения как да стигнем от всеки връх до всеки друг, можем да намерим свързаната компонента на произволен връх доста лесно: правим търсене в дълбочина или в ширина, започвайки от него, като всички посетени върхове ще са част от неговата свързана компонента. За да разбием даден граф на свързани компоненти е нужно просто за всеки от върховете му да проверим дали вече е в някоя компонента, и ако не е, да намерим неговата компонента пускайки DFS или BFS от него.

Тъй като всеки връх участва в точно една компонента, и, съответно, бива разглеждан заедно със своите ребра точно по веднъж, сложността за намиране на всички компоненти на графа е O(N + M).

Примерен код, който разбива граф на компоненти:
TODO

Силно-свързани компоненти

Силно-свързана компонента наричаме максимално подмножество от върхове в насочен граф, между всеки два от които има път.

Забележете, че единственото различно нещо от дефиницията за свързана компонента е, че тук графът е насочен. Това, обаче, променя значително нещата, тъй като когато графът е насочен, е възможно да можем да стигнем от връх A до връх B, но не и от връх B до връх A по дадените ребра на графа.

Нещо повече, по дадената дефиниция е възможно два върха да имат ребро помежду си, но да не принадлежат на една и съща силно-свързана компонента! Погледнете следния пример:
TODO: Примерен граф
TODO: Текст, описващ между кои върхове има ребро, но не принадлежат на една компонента.

Намирането на силно-свързани компоненти става по-трудно, но все пак съществуват не твърде сложни алгоритми за това. В зависимост от това колко бърз искаме да е алгоритъмът, съществуват няколко възможности (всяка по-сложна, но и по-бърза от предходната).

Наивен алгоритъм - O(2 * (N+M))

За всеки връх, който все още не принадлежи на силно-свързана компонента, пускаме DFS за да намерим достижимите от него върхове. После, за всеки от тях трябва да проверим дали можем да стигнем обратно до първоначалния. Това правим с ново DFS от всеки от достижимите върхове.
?"Редки" ("sparse") графи се наричат графи, в които броят на ребрата не е много по-голям от броя на върховете - което много често е случаят както в състезателни, така и в задачи от реалния живот. В състезателни задачи почти винаги ограничението на върховете е под 200,000, а на ребрата - под 500,000, при теоретичен максимум от 40,000,000,000.
Тъй като правим това потенциално за всеки връх (O(N)), и от всеки връх достигаме потенциално всички други (O(N)), като за всеки от достигнатите пускаме ново DFS (O(N+M)), сложността на това решение е O(N2∙(N+M)). В граф, в който от всеки връх има ребра към всички върхове с по-голям индекс, ще имаме N * (N - 1) / 2 ребра, и, съответно, този алгоритъм би бил О(N4).
В редки (sparse) графи, което е входът в почти всички състезателни задачи, сложността можем да считаме за O(N3).

По-умен алгоритъм - O(N * (N+M))

Голяма част от времето в горния алгоритъм се губи при проверката кои от достижимите върхове имат път обратно до началния. С малко съобразителност можем да видим, че това може да стане значително по-бързо с едно единствено DFS (за всеки начален връх) започвайки отново от "началния" връх, но движейки се по обратните ребра. Така, реално, с един единствен пас (за O(N+M)) намираме от кои върхове можем да стигнем до началния. Така сложността за намиране на всяка силно-свързана компонента става O(N+M) (две DFS-та), а сложността за намиране на всички силно-свързани компоненти - O(N∙(N+M)). При достатъчно гаден граф това може да стане О(N3), но за sparse графи сложността можем да считаме за O(N2).

Ефективни имплементации (О(N + M))

Ако търсите в интернет как ефективно да намирате силно-свързаните компоненти на граф, най-вероятно първият резултат ще е за алгоритъма на Таржан, който от една страна е първият измислен алгоритъм с линейна сложност, а от друга - и на практика е по-ефективен (има по-ниска константа) от повечето от останалите по-късно измислени линейни алгоритми.

Все пак, той е по-сложен за имплементация от този, който ще покажем тук, а разликата в константата е достатъчно малка за да не си заслужава по-сложната имплементация. Допълнително, алгоритъмът, който ще покажем в тази тема, има "added benefits" в някои от употребите си (например, за решаване на 2-SAT проблема, което ще разгледаме по-късно).

Алгоритъм на Косаражу

Алгоритъмът на Kosaraju, подобно на по-умния наивен алгоритъм, който показахме по-горе, ползва два типа DFS-та – едно по правите ребра в графа, и едно по обратните. За разлика от него, обаче, го правим по такъв начин, че всеки връх да бъде посетен точно по два пъти – веднъж в някое от DFS-тата по правите ребра и веднъж в някое от DFS-тата по обратните ребра. Така неговата сложност е едва O(N+M), правейки го оптимален (наистина, няма как да намерим силно-свързаните компоненти на граф, без да разгледаме всеки връх и всяко ребро поне по веднъж).

Идея

Подобно на оптимизирания наивен алгоритъм, и тук идеята е да вземаме върхове, които все още не са в силно-свързана компонента, и да намираме компонентата им. Това правим като на първа стъпка намираме достижимите от тях върхове, а на втора – кои от достижимите могат да стигнат обратно до началния. В случая, обаче, ще направим първата стъпка за всички върхове, преди да започнем с втората стъпка, с която намираме самите компоненти.

Алгоритъм

Първата стъпка от алгоритъма е да обходим всички върхове и да им сложим "приоритет". Обхождането правим с DFS по правите ребра в графа, започвайки от все още непосетени върхове (такива, без приоритет). Слагаме нарастващи приоритети обратно на реда, в който посещаваме върховете (тоест слагаме приоритет чак когато излизаме от рекурсията). Така даден връх ще има по-голям приоритет от всички деца в поддървото си (всички върхове, които могат да бъдат достигнати от него).

След като сме сложили приоритети на всички върхове в графа, почваме да правим втората стъпка в алгоритъма, която е да направим второ обхождане на върховете с DFS-та по обратните ребра в графа. Във втората стъпка има значение как избираме началните върхове - този път започваме от (все още непосетените) върхове с най-висок приоритет. Започвайки от даден връх X, слагаме в компонентата на X всички достижими по обратните ребра от него върхове, които все още не принадлежат на компонента.

Обхождайки началните върхове в намаляващ приоритет, при това винаги отивайки във върхове, които все още не са в никоя компонента, си гарантираме, че:
  1. Никога не отиваме във връх с по-голям приоритет от началния (тъй като той вече ще е с определена компонента).
  2. Всеки връх бива посетен точно по веднъж (тъй като в момента, в който го посетим, го вкарваме в текущата компонента, тоест по-късно нито го разглеждаме като начален, нито го обхождаме в следващи DFS-та).
Може би не е много очевидно защо движейки се по обратните ребра достигаме единствено върхове, които са от силно-свързаната компонента на текущия начален връх. Тъй като всички посетени върхове са с по-малък приоритет, то те са потенциално негови наследници от DFS-то от първата стъпка. Възможно ли е, обаче, да са били наследници на други върхове, които просто са били разгледани преди текущия начален? Не, защото реално текущият е достижим от тях по правите ребра, тоест е щял да бъде отбелязан с по-малък приоритет от тях при DFS-тата от първата стъпка.

Тъй като посещаваме всеки връх (и неговите ребра) точно по два пъти, сложността за намиране на всички силно-свързани компоненти е O(N + M), което можем да считаме за O(N) в sparse графи.

Имплементация

Чест трик при имплементацията на алгоритъма е да ползваме структурата данни стек за да пазим приоритетите на върховете от първата стъпка. Реално, тъй като всички върхове са с различен приоритет, и по-ранно посетени върхове са с по-висок приоритет от по-късно посетени такива, то можем просто да вкарваме върховете в един стек в момента, в който излизаме от DFS-то за тях. След това изкарвайки ги от стека (в ред обратен на този, в който сме ги вкарали) си гарантираме, че ги обхождаме точно в намаляващ ред на техния приоритет.

Нека представяме графа със следните данни:
int
numNodes
;
vector
<
int
>
outEdges[MAX]
,
inEdges[MAX]
;
  • numNodes е броят върхове в графа (индексирани от нула)
  • outEdges[node] е списък с излизащите ребра от връх node ("правите" ребра)
  • inEdges[node] е списък с влизащите ребра във връх node ("обратните" ребра)

Нужните данни за алгоритъма на Косаражу са следните:
bool
vis[MAX]
;
stack
<
int
>
priority
;
int
component[MAX]
,
nextComponent
;
Малко пояснения:
  • vis е масив с булеви флагове кои върхове вече са били обходени
  • priority е споменатият стек, който съхранява върховете в правилния приоритет
  • component указва в коя компонента е всеки връх
  • nextComponent указва номера на следващата компонента

Първата стъпка от алгоритъма – да намерим приоритетите на върховете (в случая – да ги вкараме в един стек) правим с DFS по правите ребра:
void
forwardRecurse(
int
node) { vis[node]
=
true
;
for
(
int
i
=
0
;
i
<
(
int
)outEdges[node].size()
;
i
+
+
)
if
(
!
vis[outEdges[node][i]]) forwardRecurse(outEdges[node][i])
;
priority.push(node)
;
}
Забележете, че маркираме върховете като посетени в началото на рекурсията (за да не ги посетим повече от веднъж), но ги добавяме в стека с приоритетите чак накрая (за да може всеки връх да е с по-голям приоритет от всичките си наследници).

Втората стъпка – да обходим върховете по приоритет и за всеки, който все още не е в компонента, да намерим неговата компонента - става с DFS по обратните ребра:
void
backwardRecurse(
int
node) { component[node]
=
nextComponent
;
for
(
int
i
=
0
;
i
<
(
int
)inEdges[node].size()
;
i
+
+
)
if
(component[inEdges[node][i]]
=
=
-
1
) backwardRecurse(inEdges[node][i])
;
}
Тук ползваме масива с компонентите като индикатор дали даден връх вече е бил посетен или не.

Самото извикване на DFS-тата правим по следния начин:
void
kosaraju() { memset(vis
,
0
,
sizeof
(vis))
;
for
(
int
node
=
0
;
node
<
numNodes
;
node
+
+
)
if
(
!
vis[node]) forwardRecurse(node)
;
nextComponent
=
0
;
memset(component
,
-
1
,
sizeof
(component))
;
while
(
!
priority.empty()) {
int
node
=
priority.top()
;
priority.pop()
;
if
(component[node]
=
=
-
1
) { backwardRecurse(node)
;
nextComponent
+
+
;
} } }
В края на изпълнението на функцията kosaraju() компонентата на всеки от върховете е зададена в масива component.

Много хубаво обяснение по малко по-различен начин (на английски) можете да намерите тук.

Задачи

В чист вид намирането на силно-свързани компоненти рядко се среща в състезателни задачи (тъй като е относително прост, сам по себе си). Обикновено се използва като стъпка в по-сложни задачи, или като част от по-сложен алгоритъм. Негова употреба в задачи за удовлетворяване на булеви изрази ще видим в темата за това.

Все пак, задачи, в които ви трябва, са, например, TODO и TODO. В задачата TODO пък трябва да намерите силно-свързаните компоненти на графа и да ги "слеете" във върхове, като полученият граф става насочен, ацикличен граф (DAG), в който можете да приложите динамично оптимиране.

Допълнителни материали

  1. Силно-свързани компоненти (en.wikipedia.org)
  2. Алгоритъм на Таржан (en.wikipedia.org)
  3. Алгоритъм на Косаражу (en.wikipedia.org)
  4. Алгоритъм на Косаражу (cp-algorithms.com)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 106 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: