El uso de una estructura de datos disjuntos se puede conectar fácilmente al componente de gráfico. Y, simplemente es compatible con Incremental Connected Components.cómo encontrar el componente conectado dinámicamente
Sin embargo, en mi caso, la eliminación de borde es muy común, por lo que yo estoy buscando un algoritmo o una nueva estructura puede mantener los componentes en red totalmente dinámica (incluyendo la adición y eliminación de bordes)
Gracias
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001) proporciona un algoritmo que permite una secuencia arbitraria de inserciones de bordes, eliminaciones y consultas de conectividad, con actualizaciones (inserciones y eliminaciones) que toman O (log (n)^2) tiempo amortizado y consultas que toman O (log (n)/log (log (n))) time, donde n es el número de vértices en el gráfico. Estos límites de tiempo suponen que el gráfico comienza sin bordes.
sólo desnatada el primer 2 de sus 38 páginas, pero no ser (también) asustado - el documento describe un montón de nuevos algoritmos en gráficos dinámicos (es decir, los gráficos que se puede modificar de manera eficiente durante tiempo) cuya conectividad es la más simple.
[El artículo de Wikipedia] (http://en.wikipedia.org/wiki/Connected_component_ (graph_theory)) tiene una referencia. –
@ n.m. ¿cúal? "Conectividad no dirigida en el espacio de registro"? – Chang
"Un problema de borrado de bordes en línea" –