Алгоритам за налажење компоненти повезаности

У теорији графова, компоненте повезаности усмереног графа могу бити нађене користећи алгоритам који врши претрагу у дубину у комбинацији са два стека: један који памти чворове у датој компоненти (повезаности) и други који памти чворове у текућој претрази у дубину. Неке верзије алгоритма предложили су Purdom 1970, Munro 1971, Dijkstra 1976, Cheriyan & Mehlhorn 1996, и Gabow 2000; од ових, Дијкстрин алгоритам је био први који је постигао линеарно време.

Опис

Алгоритам прво уради претрагу у дубину датог графа G, користећи два стека S и P. Стек S садржи све чворове који још увек нису приписани ниједној компоненти повезаности, у поретку у ком их претрага у дубину смешта на стек. Стек P садржи чворове за које још није утврђено да припадају различитим компонентама повезаности. Такође користи бројач С- број до сада смештених чворова, који користи да би утврдио бројеве чворова у preorder обиласку.

Када претрага у дубину дође до чвора v, алгоритам ради следеће:

Поставља С на број чвора v пре уређивања и инкрементира С.
Ставља v на стек S i P.
За сваки чвор у који је сусед чвора в:
- Ако чвору у још увек није постављен број по preorder обиласку, рекурзивно претражи у;
- Иначе, ако у још увек није придружен компоненти повезаности:
  - Скида чвор са стека Р све док се на врху стека појави елемент који има preorder број мањи или једнак preorder броју чвора у.
Ако је v највиши елемент стека Р:
- Скида елемент са стека S све док не скине чвор v и скинуте чворове придружује новој компоненти повезаности.
- Скида v са стека Р.

Главни алгоритам састоји се од петље која обилази чворове графа и позива ову рекурзивну претрагу за сваки чвор коме још увек није додељен број добијен preorder обиласком.

Повезани алгоритми

Као и горе поменути, Тарјанов алгоритам за налажење компоненти повезаности, такође користи претрагу у дубину заједно са стеком који памти који чворови још увек нису додељени ниједној компоненти повезаности, и који придружује ове чворове новој компоненти када се тренутна компонента не може више проширити. Међутим, уместо другог стека, Тарјанов алгоритам користи низ претходно уређених бројева, помоћу ког одређује кад треба формирати нову компоненту.

Литература

Cheriyan, J.; Mehlhorn, K. (1996), „Algorithms for dense graphs and networks on the random access computer”, Algorithmica, 15: 521—549, doi:10.1007/BF01940880 .
Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25 .
Gabow, Harold N. (2000), „Path-based depth-first search for strong and biconnected components”, Information Processing Letters, 74 (3-4): 107—114, MR 1761551, doi:10.1016/S0020-0190(00)00051-X .
Munro, Ian (1971), „Efficient determination of the transitive closure of a directed graph”, Information Processing Letters, 1: 56—58 .
Purdom, P., Jr. (1970), „A transitive closure algorithm”, BIT, 10: 76—94 .
Sedgewick, R. (2004), „19.8 Strong Components in Digraphs”, Algorithms in Java, Part 5 – Graph Algorithms (3rd изд.), Cambridge MA: Addison-Wesley, стр. 205—216 .

Референце