Der beste Weg für die gesamte Erreichbarkeit zu testen

Question

Ich habe eine Reihe von Knoten, von denen jeder mit mindestens einem anderen Knoten verbunden ist. Ich würde gerne wissen, ob die Verbindungen sind, so dass jeder Knoten von jedem anderen erreichbar ist. Zum Beispiel:

1--2
   |
3--4

Versus:

1--2

3--4

Ich bin überzeugt, diese Art von Erreichbarkeitsprüfung kann in Bezug auf eine genaue Abdeckung projiziert werden , aber ich kann nicht mein Gehirn eingewickelt werden um scheinen, wie dies zu tun. Hat jemand irgendwelche Hinweise, Dokumentation, Websites, etc. auf, wie dies zu tun? Beispiele hierfür wären äußerst wertvoll sein.

Update: Meine Ignoranz mich verraten hat, wie es scheinen würde wesentlich effiziente Algorithmen für diese Art von Test geben. Wenn Sie eine haben, zeigen Sie mir bitte zu.

Answer 1

• von jedem Knoten startet und eine Tiefe / Breite ersten Traversierung tun
• count Anzahl der besuchten Knoten (natürlich nicht zweimal jeden Knoten besuchen!)
• vergleichen gezählte Anzahl mit Gesamtzahl

Answer 2

Es gibt auch ein schnellen (aber ziemlich kompliziert) Algorithmus für die Aufrechterhaltung der Konnektivität dynamisch (dh unter Rande Einfügungen / Löschungen), in diesem Papier gezeigt: Poly-logarithmische deterministisch voll dynamische Algorithmen für die Konnektivität, minimaler Spannbaum, 2-Kante und biconnectivity

Die Grundidee ist die Aufrechterhaltung eines Spanning Tree. Die einfachen Fälle sind Insertieren eine Kante, und eine nicht Spanning Tree Kante zu löschen. Das Problem ist, wenn eine Spanning-Tree-Kante zu löschen, denn jetzt ist es nicht Konnektivität garantiert -. Wir effizient eine alternative Route suchen haben die defekten Teile zu verbinden, da sonst der Graph nicht verbunden ist