Il modo migliore per testare la raggiungibilità totale

Question

Ho una serie di nodi, ognuno dei quali è connesso ad almeno un altro nodo.Vorrei sapere se le connessioni sono tali che ogni nodo sia raggiungibile da ogni altro.Per esempio:

1--2
   |
3--4

Contro:

1--2

3--4

Sono convinto che questo tipo di test di raggiungibilità possa essere progettato in termini di an problema esatto della copertina, tuttavia non riesco a capire come farlo.Qualcuno ha indicazioni, documentazione, siti web, ecc. su come farlo?Gli esempi sarebbero estremamente preziosi.

Aggiornamento: La mia ignoranza mi ha tradito, in quanto sembrerebbe che esistano algoritmi molto più efficienti per questo tipo di test.Se ne hai uno, per favore indicamelo.

Answer 1

• iniziare da qualsiasi nodo e fare una profondità / larghezza primo attraversamento
• numero di conteggio di nodo visitato (naturalmente, non lo visita ogni nodo due volte!)
• confrontare numero contato con il numero totale

Answer 2

Esiste anche un algoritmo veloce (ma piuttosto complicato) per mantenere la connettività dinamicamente (ad es.sotto inserimenti/eliminazioni di bordi), mostrato in questo documento: Algoritmi completamente dinamici deterministici polilogaritmici per connettività, albero di copertura minimo, 2-edge e biconnettività

L'idea di base è mantenere uno spanning tree.I casi più semplici sono l'inserimento di un bordo e l'eliminazione di un bordo dell'albero non spanning.Il problema sorge quando si elimina il bordo di un spanning tree, perché ora non è garantita la connettività: dobbiamo cercare in modo efficiente un percorso alternativo per connettere le parti rotte, altrimenti il ​​grafico viene disconnesso.