Dudas Prim / Kruskal

[tomastrivino]

Holaa,
estaba viendo las cápsulas del curso sobre Prim y Kruskal y usaron el mismo ejercicio de ejemplo, siendo el siguiente:

En vista de esto me surge una duda: Entendiendo que Prim y Kruskal hacen lo mismo (construir un MST dado un grafo no dirigido), ¿bajo qué casos me sería más conveniente usar uno antes que otro? ¿queda a criterio? Pregunto especialmente porque ambos tienen una complejidad de $\approx O(E log(V))$

En relación a la pregunta anterior, también vimos el siguiente ejercicio:

Para este en particular, ¿se puede resolver usando el algoritmo Kruskal? ¿por qué sí o por qué no?

Adicionalmente, vimos dos pseudocódigos de Prim, siendo el primero

Y luego uno más concreto:

Nuevamente me surge la duda de cuál utilizar, en adición a ¿En qué se argumenta que el segundo sea más concreto? ¿Qué vendría a prevenir (quizás) la línea 6 o el ver los colores?

Gracias desde ya!! :D

[isabellacherubini]

Hola!
Sobre tu primera pregunta, la decisión sobre que algoritmo utilizar va a depender de la implementación que quieras realizar. Como mencionas, ambos tienen una complejidad similar, por lo que la decisión va a depender de las características del problema en específico, pensando en las diferencias de implementación que tiene cada uno.
Para tu segunda pregunta, si es posible realizar el problema con el algoritmo de kruskal, similar a la implementación de prim, podemos usar union find con las aristas nuevas que se introducen al problema para encontrar la solución.
Sobre lo último, podemos decir que el segundo es más concreto porque estamos modificando directamente el nodo, a diferencia del primer algoritmo. Sobre el tema de la línea, no me queda claro a cual de los dos códigos te refieres.
Cualquier cosa que no quede claro avísame :)

[tomastrivino]

Gracias :)