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

Из Википедије, слободне енциклопедије

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

Опис[уреди]

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

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

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

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

Повезани алгоритми[уреди]

Као и горе поменути, Тарјанов алгоритам за налажење компоненти повезаности, такође користи претрагу у дубину заједно са стеком који памти који чворови још увек нису додељени ниједној компоненти повезаности, и који придружује ове чворове новој компоненти када се тренутна компонента не може више проширити. Међутим, уместо другог стека, Тарјанов алгоритам користи низ 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, DOI:10.1016/S0020-0190(00)00051-X, MR 1761551 .
  • 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 ed.), Cambridge MA: Addison-Wesley, pp. 205–216 .