Algoritmo de prim y kruskal

Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemosdefinir un árbol como:
o Un grafo conexo y sin ciclos.
o Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
[pic]
• Grado de un nodo en un árbol es el númerode subárboles de aquel nodo (en el ejemplo, el grado de v1 es 2 y de v2 1).
• Denominamos hojas en un árbol a los nodos finales (v3, v5 y v6).
• Un árbol de máximo alcance es aquel queobtenemos en un grafo conexo y sin ciclos.
• Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima.
• Algoritmo de Kruskal: Elalgoritmo de Kruskal permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos:
1. Se marca la arista con menor valor. Si hay más de una, seelige cualquiera de ellas.
2. De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas.
3. Repetir el paso 2 siempre que laarista elegida no forme un ciclo con las ya marcadas.
4. El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos,siendo n el número de nodos del grafo.
• Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:
[pic]
Siguiendo el algoritmo de Kruskal, tenemos:
o Elegimos,por ejemplo, la arista (5, 6) = 1 (menor valor) y la marcamos.
o Elegimos la siguiente arista con menor valor (1, 3) = 1 y la marcamos.
o Elegimos la siguiente arista con menor valor(5, 7) = 2 y la marcamos, ya que no forma ciclos con ninguna arista de las marcadas anteriormente.
o Elegimos la siguiente arista con menor valor (1, 2) = 3 y la marcamos, ya que no forma...