La meilleure façon de tester joignabilité totale

Question

I ai un ensemble de noeuds, dont chacun est relié à au moins un autre noeud. Je voudrais savoir si les connexions sont telles que chaque nœud est accessible à partir de tous les autres. Par exemple:

1--2
   |
3--4

Versus:

1--2

3--4

Je suis convaincu que ce genre de test de joignabilité peut projeter en termes d'un problème de couverture exacte , mais je ne peux pas sembler obtenir mon cerveau enroulé autour de la façon de le faire. Quelqu'un at-il des pointeurs, documentation, sites Web, etc., sur la façon de le faire? Des exemples seraient extrêmement précieux.

Mise à jour: Mon ignorance m'a trahi, car il semblerait qu'il existe des algorithmes beaucoup plus efficaces pour ce genre de test. Si vous en avez un, s'il vous plaît me l'indiquent.

Answer 1

• commencer à partir de tout nœud et faire un rapport profondeur / largeur d'abord traversal
• numéro de compte du noeud visité (bien sûr, ne pas visiter un noeud deux fois!)
• comparer avec nombre compté nombre total

Answer 2

Il y a aussi un rapide (mais assez compliqué) algorithme pour maintenir la connectivité dynamique (c.-à-sous insertions de bord / suppressions), présentés dans ce document: algorithmes Poly-logarithmique entièrement dynamiques déterministes pour la connectivité, arbre couvrant minimal, 2-bord et biconnectivity

L'idée de base est de maintenir un arbre couvrant. Les cas faciles sont l'insertion d'un bord, et la suppression d'un bord d'arbre non Spanning. Le problème est lors de la suppression d'un bord spanning tree, parce que maintenant il n'y a pas garanti la connectivité -. Nous devons rechercher efficacement un autre itinéraire pour relier les pièces cassées, sinon le graphique est déconnecté