¿Por qué falla el algoritmo MST de Prim y Kruskal para Directed Graph?

Requisitos previos:

• Gráfico y sus representaciones
• Algoritmos codiciosos | Conjunto 5 (Árbol de expansión mínimo (MST) de Prim)
• Algoritmo de árbol de expansión mínimo de Kruskal | Codicioso Algo-2

Dado un grafo dirigido D = < V, E > , la tarea es encontrar el árbol generador mínimo para el grafo dirigido dado

Ejemplo:

Pero el árbol de expansión mínimo de Prim y el algoritmo de Kruskal fallan para gráficos dirigidos. Veamos por qué

¿Por qué falla el algoritmo de Prim para el gráfico dirigido?

El algoritmo de Prim asume que todos los vértices están conectados. Pero en un gráfico dirigido, no se puede acceder a todos los Nodes desde todos los demás Nodes. Entonces, el algoritmo de Prim falla por esta razón.
Por ejemplo:

Como se ve en el gráfico, no se puede acceder a ningún Node desde el Node 4. Los gráficos dirigidos no cumplen el requisito de que todos los vértices estén conectados.

¿Por qué el algoritmo de Kruskal falla para el gráfico dirigido?
En el algoritmo de Kruskal, en cada paso, se comprueba que si las aristas forman un ciclo con el árbol de expansión formado hasta el momento. Pero el algoritmo de Kruskal no detecta los ciclos en un gráfico dirigido, ya que hay casos en los que no hay ciclo entre los vértices, pero el algoritmo de Kruskal asume que es un ciclo y no tiene en cuenta algunos bordes debido a que el algoritmo de Kruskal falla para el gráfico dirigido.
Por ejemplo: se informará que este gráfico contiene un ciclo con el método Union-Find, pero este gráfico no tiene ciclo.

El equivalente del árbol de expansión mínima en gráficos dirigidos es, «Arborescencia de expansión mínima» (también conocida como ramificación óptima) puede resolverse mediante el algoritmo de Edmonds con un tiempo de ejecución de O (EV). Este algoritmo es análogo al problema del árbol de expansión mínimo.