Robím svoj výskum a zasekávam sa otázkou:
Mám minimálny preklenovací strom (primárny algoritmus), teraz sa odstráni jeden uzol v mojom strome, zaujímalo by ma, či existuje spôsob, ako môžem znova usporiadať strom tak, aby sa zachovala optimalita?
Hľadám tu niekoľko návrhov a ocenia vašu pomoc.
Ďakujem!
odpovede:
2 pre odpoveď č. 1Tento problém bol dobre preštudovaný. Výskum uskutočnený v roku 2001 našiel spôsob, ako udržiavať štruktúru dát grafu, takže môžete vložiť alebo odstrániť hranu a aktualizovať minimálny preklenovací strom v čase O (log4 n), ktoré sú podľa môjho najlepšieho vedomia najlepšiečasovo ohraničený, s ktorým sa doteraz dokázal prísť. Príspevok popisujúci tento algoritmus je hustý a zložitý, ale ak vás zaujíma, nájdete ho tu:
Dúfam, že to pomôže!
1 pre odpoveď č. 2
Keď odstránite uzol zo stromu, môže sa rozdeliťgraf na viac ako jeden odpojený komponent. V najhoršom prípade si predstavte MST, kde všetky hrany prechádzajú od jedného centrálneho uzla k všetkým ostatným - ako hviezda. V takom prípade, ak sa odstráni centrálny uzol, bude potrebné prepracovať celý MST. Myslím, že krátka odpoveď je - záleží na tom, ktorý uzol sa odstráni. Riešením je urobiť to ako aix uvedené - nájdite všetky komponenty, ktoré sú odpojené kvôli odstránenému uzlu a nenásytne ich spojte. To by sa mohlo rozprestierať od 0 (ak je odstránený listový uzol) do n-1 (ak je odstránený stred hviezdy)
-1 pre odpoveď č. 3
Ak bol odstránený vrchol listom MST, nemusíte robiť nič: stále máte preklenovací strom a je to stále optimálne.
Keby to nebol list, teraz máte dva pod stromami. Všetko, čo musíte urobiť, je znovu ich spojiť podľa najkratšej hrany, ktorá existuje medzi dvoma podrežami. Najlepší spôsob, ako zistiť, že hrana je pravdepodobne pomocou akejkoľvek dátovej štruktúry, ktorú ste použili pre Primov algoritmus (alebo, triviálne, v O (n ^ 2), berúc do úvahy všetky páry vrcholov).