Qual é o algoritmo e a estrutura de dados mais eficientes para manter as informações dos componentes conectados em um gráfico dinâmico?

Digamos que eu tenha um gráfico esparso finito não direcionado e precise executar as seguintes consultas com eficiência:

• - retornos T , se existir um caminho entre N 1 e N 2 , de outro modo$IsConnected(N_1, N_2)$$T$$N_1$$N_2$$F$
• - retorna o conjunto dos nós que são acessíveis a partir de$ConnectedNodes(N)$$N$

Isso é feito facilmente pré-computando os componentes conectados do gráfico. Ambas as consultas podem ser executadas no tempo .$O(1)$

Se também precisa de ser capaz de adicionar bordas arbitrariamente - -, em seguida, que pode armazenar os componentes em uma estrutura de dados disjuntos-conjunto . Sempre que uma aresta é adicionada, se conectar dois nós em componentes diferentes, eu mesclaria esses componentes. Isso adiciona custo O ( 1 ) a A d d E d g e e O ( I n v e r s e A c $AddEdge(N_1, N_2)$$O(1)$$AddEdge$ custo de I s C o n n e c t e d e C o n n e c t e d N o d e s (o qual pode também ser O ( 1 ) ).$O(InverseAckermann(|Nodes|))$$IsConnected$$ConnectedNodes$$O(1)$

Se eu também precisar remover arestas arbitrariamente, qual é a melhor estrutura de dados para lidar com essa situação? Alguém é conhecido? Para resumir, ele deve oferecer suporte às seguintes operações com eficiência:

• - retornos T , se existir um caminho entre N 1 e N 2 , de outro modo F .$IsConnected(N_1, N_2)$$T$$N_1$$N_2$$F$
• - retorna o conjunto dos nós que são acessíveis a partir de N .$ConnectedNodes(N)$$N$
• - adiciona uma aresta entre dois nós. Observe que N 1 , N 2 ou ambos podem não ter existido antes.$AddEdge(N_1, N_2)$$N_1$$N_2$
• - remove uma aresta existente entre dois nós.$RemoveEdge(N_1, N_2)$

(Estou interessado nisso da perspectiva do desenvolvimento do jogo - esse problema parece ocorrer em várias situações. Talvez o jogador possa construir linhas de força e precisamos saber se um gerador está conectado a um prédio. Talvez o jogador possa bloquear e destrancar portas, e precisamos saber se um inimigo pode alcançar o jogador. Mas é um problema muito geral, então eu o expressei como tal)

Esse problema é conhecido como conectividade dinâmica e é uma área ativa de pesquisa na comunidade teórica da ciência da computação. Ainda alguns problemas importantes ainda estão abertos aqui.

Para esclarecer a terminologia, solicite conectividade totalmente dinâmica, pois você deseja adicionar e excluir arestas. Há um resultado de Holm, de Lichtenberg e Thorup (J.ACM 2001) que alcança$O(\log^2 n)$ hora de atualização e $O(\log n / \log\log n)$tempo de consulta. Pelo meu entendimento, parece ser implementável. Simplesmente falando, a estrutura de dados mantém uma hierarquia de árvores abrangidas - e a conectividade dinâmica nas árvores é mais fácil de cobrir. Posso recomendar as anotações de Erik D. Demaine para uma boa explicação, veja aqui um vídeo. A nota de Erik também contém indicadores para outros resultados relevantes. Nota: todos esses resultados são teóricos.

Essas estruturas de dados podem não fornecer consultas ao ConnectedNodes por si só, mas é fácil conseguir isso. Basta manter como estrutura de dados adicional o gráfico (por exemplo, lista de arestas duplamente conectadas) e fazer a pesquisa em profundidade para obter os nós que podem ser alcançados a partir de um determinado nó.