La pregunta es un poco confusa, pero la entiendo así:
Desea crear un gráfico aleatorio con N nodos y M bordes (donde M es aleatorio) y quiere asegurarse de que su gráfico aleatorio esté conectado.
Primero, debe asegurarse de que M sea al menos igual a N-1. Si M es más pequeño que N-1, no hay forma de que puedas hacer un gráfico conectado. Dicho esto, lo primero que tienes que hacer es crear un árbol .
- ¿Las estructuras en lenguaje C son similares a los objetos en Java?
- Cómo implementar Dropconnect usando TensorLayer
- ¿El algoritmo de Dios realmente funciona en el Cubo de Rubik 3x3x3?
- Cómo realizar una operación de revolución usando un treap
- ¿La programación competitiva se volverá aún más difícil?
Es fácil crear un árbol aleatorio, puede hacer un algoritmo iterativo que realiza pasos N-1 y, en cada paso, conecta dos nodos que aún no están conectados agregando un borde entre ellos. De esta manera, después de los pasos N-1, tendrá un árbol, que ya es un gráfico conectado. Para verificar si dos nodos están conectados, puede usar una estructura de datos de búsqueda de unión para obtener la máxima eficiencia.
Ahora que tiene un árbol con bordes N-1, puede llenar su árbol con bordes aleatorios (entonces ya no será un árbol, pero obviamente sigue siendo un gráfico conectado) hasta que tenga exactamente M bordes.
