- Seleccionar inicialmente cualquier nodo y conectarlo el mas próximo que contenga la arista de menor costo o distancia. A esta rama se le acepta como parte de la red final.
- Completar la red interactiva mente, identificando el nodo no conectado que esta mas cerca o menos costo de alguno de los nodos conectados, se consideran todas las ramas que conectan a estos nodos con nodos inconexos.
- Agregar a este nodo al conjunto de nodos conectando. en caso de empate este se rompe en forma arbitraria.
- En cada etapa del proceso iterativo la atención se centra en aquellos nodos que ya se han eslabonados. Repetir este paso hasta que se hayan conectado todos los nodos.
Ejemplo:
Este es el grafo ponderado de partida. No es un árbol, ya que para serlo se requiere que no haya ciclos, y en este caso sí 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.
No visto
En el grafo
En el árbol
C,
G
A, B,
E, F
D
0
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.
No visto
En el grafo
En el árbol
C,
G
B, E,
F
A, D
5
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.
No visto
En el grafo
En el árbol
C, G
B, E,
A, D,
F
5 + 6
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.
No visto
En el grafo
En el árbol
null
C, E,
G
A, D,
F, B
5 + 6 + 7
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.
No visto
En el grafo
En el árbol
null
C, G
A, D,
F, B, E
5 + 6 + 7 + 7
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.
No visto
En el grafo
En el árbol
null
G
A, D,
F, B, E, C
5 + 6 + 7 + 7 + 5
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ínima se muestra en verde. En este caso con un peso de 39.
No visto
En el grafo
En el árbol
null
null
A, D,
F, B, E, C, G
5 + 6 + 7 + 7 + 5 + 9
Al final queda el árbol de expansión mínima.
5 + 6 + 7 + 7 + 5 + 9 = 39
- Seleccionar inicialmente cualquier nodo y conectarlo el mas próximo que contenga la arista de menor costo o distancia. A esta rama se le acepta como parte de la red final.
- Completar la red interactiva mente, identificando el nodo no conectado que esta mas cerca o menos costo de alguno de los nodos conectados, se consideran todas las ramas que conectan a estos nodos con nodos inconexos.
- Agregar a este nodo al conjunto de nodos conectando. en caso de empate este se rompe en forma arbitraria.
- En cada etapa del proceso iterativo la atención se centra en aquellos nodos que ya se han eslabonados. Repetir este paso hasta que se hayan conectado todos los nodos.
Ejemplo:
No visto
|
En el grafo
|
En el árbol
|
C,
G
|
A, B,
E, F
|
D
|
0
No visto
|
En el grafo
|
En el árbol
|
C,
G
|
B, E,
F
|
A, D
|
5
No visto
|
En el grafo
|
En el árbol
|
C, G
|
B, E,
|
A, D,
F
|
5 + 6
No visto
|
En el grafo
|
En el árbol
|
null
|
C, E,
G
|
A, D,
F, B
|
5 + 6 + 7
No visto
|
En el grafo
|
En el árbol
|
null
|
C, G
|
A, D,
F, B, E
|
No visto
|
En el grafo
|
En el árbol
|
null
|
G
|
A, D,
F, B, E, C
|
5 + 6 + 7 + 7 + 5
No visto
|
En el grafo
|
En el árbol
|
null
|
null
|
A, D,
F, B, E, C, G
|
5 + 6 + 7 + 7 + 5 + 9 = 39
0 comentarios :
Publicar un comentario