Melhor maneira de testar para a acessibilidade total de

Question

Eu tenho um conjunto de nós, cada um dos quais está ligado a pelo menos um outro nó. Gostaria de saber se as conexões estão de tal forma que cada nó é acessível a partir de todos os outros. Por exemplo:

1--2
   |
3--4

Versus:

1--2

3--4

Estou convencido de que este tipo de teste acessibilidade pode ser projetada em termos de um exato problema de cobertura , porém eu não consigo obter o meu cérebro envolvida em torno de como fazê-lo. Alguém tem qualquer ponteiros, documentação, sites, etc., sobre como fazer isso? Exemplos seriam extremamente valiosos.

Update: Minha ignorância me traiu, como parece há muito mais eficiente algoritmos para este tipo de teste. Se você tem um, por favor me aponte para ele.

Answer 1

• começar a partir de qualquer nó e fazer uma profundidade / largura primeira travessia
• contagem de número de nó visitou (claro, não visitar qualquer nó duas vezes!)
• comparar número contado com número total

Answer 2

Há também um rápido (mas bastante complicado) algoritmo para manter a conectividade dinamicamente (ou seja, sob inserções de ponta / exclusão), apresentados neste trabalho: Poly-logarítmicas deterministas algoritmos totalmente dinâmicos para conectividade, árvore mínimo abrangendo, 2 de ponta, e biconnectivity

A idéia básica é manter uma árvore de expansão. Os casos fáceis está inserindo uma vantagem e eliminar uma borda não Spanning Tree. O problema é quando a exclusão de uma borda de árvore estendida, porque agora não é garantida a conectividade -. Nós temos que procurar de forma eficiente uma rota alternativa para conectar as peças quebradas, caso contrário, o gráfico está desligado