Estoy buscando formas de mantener un árbol de expansión de un gráfico relativamente equilibrado, a medida que agrego nuevos nodos / bordes al gráfico.
Tengo un gráfico no dirigido que comienza como un solo nodo, la "raíz".
En cada paso, agrego al gráfico un nuevo nodo y un borde que lo conecta al gráfico, o simplemente un nuevo borde, que conecta dos nodos antiguos. A medida que crezco el gráfico, mantengo un árbol de expansión. La mayoría de las veces, esto significa que cuando agrego un nuevo nodo y borde, configuro el nuevo nodo para que sea el hijo del antiguo nodo al que se conecta.
No tengo control sobre el orden en que se agregan los nuevos nodos, por lo que el algoritmo de construcción de árboles anterior obviamente puede conducir a árboles de expansión desequilibrados.
¿Alguien sabe de la heurística en línea que mantendrá el árbol de expansión "relativamente equilibrado", al tiempo que minimiza la cantidad de trabajo realizado en la reorganización? Tengo control total sobre la estructura del árbol. Lo que no controlo es la conectividad gráfica, o el orden en que se agregan los nuevos nodos.
Tenga en cuenta que las respuestas estándar de Google a términos como "equilibrio", "expansión" y "árbol" parecen ser árboles binarios y árboles B, ninguno de los cuales se aplica. Mis nodos de gráfico pueden tener cualquier número de vecinos, por lo que los nodos de árbol pueden tener cualquier número de hijos, no 2 como árboles binarios. Los árboles B mantienen el equilibrio cambiando sus listas de adyacencia, y no puedo cambiar la conectividad del gráfico.
fuente
Respuestas:
Cada vez que agrega un nuevo vértice con un borde, no tiene opciones. Cada vez que agrega un nuevo borde, si la distancia actual a la raíz es mayor que la distancia a través del nuevo borde, elimina el borde anterior en la ruta más corta y agrega el nuevo. De lo contrario, simplemente mantienes tu árbol sin cambios. Creo que de esta manera obtienes algo muy similar a un árbol BFS en el sentido de que los niveles del árbol contendrán los mismos vértices y la distancia desde un vértice hasta la raíz será la misma que la distancia en el árbol BFS (y en el gráfico), pero no sé si eso es suficiente para satisfacer su condición de "árbol de expansión equilibrado ideal".
fuente
Terminé haciendo lo siguiente:
La respuesta de Vinicius Santos es la primera parte. Como él dice, en cualquier marco agrego un nuevo nodo y un borde padre-hijo que se conecta a él, o simplemente agrego un borde cruzado entre dos nodos existentes. Los bordes padre-hijo no ofrecen oportunidades para cambiar la estructura de árbol, solo los bordes cruzados lo hacen. Considere agregar un E cruzado entre los nodos A y B, donde B tiene la mayor profundidad de árbol. Si (A.depth + 1) <B.depth, entonces podemos disminuir B.depth convirtiéndolo en hijo de A.
Habiendo disminuido la profundidad de B, ahora debemos verificar a los vecinos de B, para ver si pueden disminuir su profundidad al convertirse en hijos de B. Por lo tanto, realizamos un recorrido transversal primero desde B, que atraviesa un borde de X a Y si X. profundidad + 1 <profundidad Y, y establece que Y sea hijo de X.
fuente