Modo rapido per verificare se esiste un percorso nel digraph

0

Ho un grafico diretto finito (di diversi componenti debolmente connessi).

Avendo due elementi ho bisogno di controllare se c'è un percorso dal primo al secondo.

La soluzione più semplice è creare la matrice di incidenza e quindi utilizzarla per calcolare la matrice di connettività (più è ovvio). Ma ritengo che non sia il modo più efficiente in termini di tempo di avvio e spazio di memoria.

Che cos'è un modo più efficiente (tenendo conto del fatto che ci sono diversi componenti tra i quali non ci sono collegamenti)?

Inoltre, per l'ottimizzazione si può usare quanto segue: In ogni componente connesso K, l'esistenza di un percorso deve essere verificata solo da un vertice fisso B (K) ad altri elementi solo di K. E non dovrebbe mai verificare se esiste un percorso (sappiamo che non esiste nessuno per definizione dei componenti connessi, tuttavia) da un elemento di un componente connesso a un elemento di un altro componente connesso.

Scrivo in Ada.

    
posta porton 29.10.2017 - 02:06
fonte

0 risposte

Leggi altre domande sui tag