Back

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




                                     

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

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

                                     

1. Опис

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

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

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

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

                                     

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

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

                                     

3. Референце

  • Sedgewick, R. 2004, "19.8 Strong Components in Digraphs”, Algorithms in Java, Part 5 – Graph Algorithms 3rd изд., Cambridge MA: Addison-Wesley, стр. 205 - 216.
  • Cheriyan, J.; Mehlhorn, K. 1996, "Algorithms for dense graphs and networks on the random access computer”, Algorithmica, 15: 521 - 549, doi:10.1007/BF01940880.
  • Munro, Ian 1971, "Efficient determination of the transitive closure of a directed graph”, Information Processing Letters, 1: 56 - 58.
  • 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-01900000051-X.
  • Purdom, P., Jr. 1970, "A transitive closure algorithm”, BIT, 10: 76 - 94.
                                     
  • повезана компонента садржи бар један усмерени циклус. Косарајуов алгоритам Тарџанов алгоритам и Алгоритам за налажење чврсто повезаних компоненти графа
  • U informatici i teoriji grafova, Kargerov algoritam je algoritam nasumične metode koji odreduje minimalan rez povezanog grafa. Izmislio ga je Dejvid Karger
  • najjeftinije grane izmedu svakog para komponenti posle svake faze algoritma. Stoga je ukupno očekivano vreme za ovaj algoritam O n log log n Problem može biti
  • put izmedu dva čvora, na primer ako čvorovi pripadaju različitim komponentima povezanosti smatra se da je njihovo rastojanje beskonačno. U slučaju da je

Users also searched:

...