La mejor manera de probar la accesibilidad total

Question

Tengo un conjunto de nodos, cada uno de los cuales está conectado al menos a otro nodo.Me gustaría saber si las conexiones son tales que cada nodo sea accesible desde todos los demás.Por ejemplo:

1--2
   |
3--4

Versus:

1--2

3--4

Estoy convencido de que este tipo de pruebas de accesibilidad se pueden proyectar en términos de una problema de cobertura exacta, sin embargo, parece que no puedo entender cómo hacerlo.¿Alguien tiene algún consejo, documentación, sitios web, etc., sobre cómo hacer esto?Los ejemplos serían extremadamente valiosos.

Actualizar: Mi ignorancia me ha traicionado, ya que parece que existen algoritmos mucho más eficientes para este tipo de pruebas.Si tienes uno, indícamelo.

Answer 1

• comenzar desde cualquier nodo y hacer una profundidad / anchura primera traversal
• número de recuento de nodo visitado (por supuesto, no te visitar cualquier nodo dos veces!)
• comparar número contado con el número total

Answer 2

También existe un algoritmo rápido (pero bastante complicado) para mantener la conectividad dinámicamente (es decir,debajo de inserciones/eliminaciones de bordes), que se muestra en este documento: Algoritmos polilogarítmicos deterministas totalmente dinámicos para conectividad, árbol de expansión mínimo, 2 bordes y biconectividad

La idea básica es mantener un árbol de expansión.Los casos fáciles son insertar un borde y eliminar un borde de árbol que no se extiende.El problema es al eliminar un borde del árbol de expansión, porque ahora no hay conectividad garantizada: tenemos que buscar de manera eficiente una ruta alternativa para conectar las partes rotas; de lo contrario, el gráfico se desconecta.