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.