Puedo responder una pregunta ligeramente diferente, pero relacionada.
Es fácil modificar el algoritmo de Prim para producir árboles de expansión con un diámetro menor que los árboles aleatorios. Recuerde que el algoritmo de Prim es muy similar en estructura al algoritmo de ruta más corta de una sola fuente de Dijkstra (sin pesos de borde, se puede usar Breadth-First Search), por lo que en lugar de seleccionar un borde aleatorio en cada paso, puede seleccionar un borde que Dijkstra algoritmo (o BFS, en su caso) seleccionaría. No parece haber una modificación fácil y computacionalmente eficiente del algoritmo de Kruskal con permutación inicial aleatoria para lograr esto.
En un caso más general con pesos de borde no triviales, puede formar un híbrido de algoritmos de Prim y Dijkstra calculando una combinación lineal convexa de longitud de borde (la prioridad en el algoritmo de Prim) y la longitud de ruta prospectiva (la prioridad en el algoritmo de Dijkstra). El coeficiente que controla la combinación lineal es una buena perilla para ajustar si está buscando árboles de expansión útiles. En un proyecto reciente, utilizamos este truco para encontrar árboles de expansión de baja extensión en gráficos grandes.
- ¿Cómo podemos resolver el siguiente problema en O (n)?
- ¿Cuál es el método racional (algoritmo) a seguir al votar?
- ¿Dónde debo desarrollar mi lógica, en matemáticas relacionadas con la programación?
- Cómo encontrar la ruta más corta en un gráfico no ponderado en lenguaje C
- ¿Debería evitarse siempre goto / JMP?