| Image | Descripción | No visto | En el grafo | En el árbol |
|---|---|---|---|---|
 |
Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya ciclos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida. | C, G | A, B, E, F | D |
 |
El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA. | C, G | B, E, F | A, D |
 |
El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF. | C | B, E, G | A, D, F |
 |
El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado. | null | C, E, G | A, D, F, B |
 |
Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol. | null | C, G | A, D, F, B, E |
 |
Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo. | null | G | A, D, F, B, E, C |
 |
G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39. | null | null | A, D, F, B, E, C, G |
Para que se usa
Se utiliza en una extensa variedad de campos del conocimiento, en la ingenieria informatica para diseñar redes, dentro de la programación para el diseño de circuitos.
En la electronica para el diseño de los complejos circuitos electronicos.
En la administración en el diseño de los organigramas de jerarquias.
0 comentarios: