Chcel by som vedieť, či je efektívnyalgoritmus S = F (v, G) na vytvorenie subgrafu S z DAG G = (V, E) tak, že všetky cesty v S obsahujú vrchol v V. Ak je to tak, je možné účinne rozšíriť F na F "(N, G) pre množinu vrcholov N. Som otvorený akýmkoľvek dátovým štruktúram na uloženie DAG G na začiatku.
V skutočnosti je stav, na ktorý som zabudol pridať, že G má jedinečný vrchol r bez prichádzajúcej hrany a cesta musí mať formu, kde d je vrchol bez odchádzajúcej hrany.
Ďalšia podmienka, ktorú mi chýba, je daná rozšíreným F "(N, G) tak, že pre všetky v, w z N if <r, .., v, .., w> kde w je drez, cesty <r, .., v, .., x> kde x! = w.
Mám skutočne jedno riešenie, ale nemeria, keď #V> 2000 a #N> 2.
odpovede:
1 pre odpoveď č. 1Predpokladám, že hľadáte najväčší subgraf S z G = ({r} + V + {d}, E), kde r je jedinečný zdrojový uzol a d je drez taký, že každá cesta od r do d prechádza určitým uzol v.
Môj navrhnutý algoritmus:
Nájdite všetky cesty medzi r a v použitím napr. odpovede uvedené v Nájsť cesty medzi dvoma danými uzlami?
Nájdite všetky cesty medzi v a používajte to istéalgoritmus. Keďže G je acyklické, žiadna cesta od v do d nemôže viesť späť k už nájdenej v kroku 1. Takže v výslednom grafe prejdú všetky cesty medzi r a d v.
1 pre odpoveď č. 2
Výsledný graf obsahuje uzly, ktoré sú dostupnéod v a uzlov v je prístupný od (alebo, uzly, ktoré sú dostupné z v v transponovanom subgrafe). Získanie množiny dostupných uzlov sa dá vykonať efektívne.
Toto môže byť jednoducho rozšírené pre skupinu uzlov: mali by ste ich jednoducho pridať na začiatku vyhľadávania.