MakeSet en Kruskal #196
-
|
Hola! Estoy viendo el pseudocódigo de Kruskal en el material de clase, y no entiendo la utilidad de la línea 3. ¿Me lo podrían explicar, por favor? |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 1 reply
-
|
Para verificar que una arista no forme un ciclo en el árbol, Kruskal utiliza conjuntos disjuntos, donde si los nodos de la arista a verificar están en conjuntos distintos (es decir, ambos tienen un distinto representante), considerar esta arista no forma un ciclo, por lo que si se agrega al árbol y los nodos de la arista pasan a pertenecer al mismo conjunto, en caso contrario la arista forma un ciclo, entonces no se considera. Entonces para implementar esa lógica, al principio hacemos MakeSet(v) en todos los nodos del grafo original, lo que significa que cada nodo lo estas considerando como un conjunto, donde el mismo nodo es el representante del conjunto, y a medida que va iterando el algoritmo, los conjuntos se van a ir uniendo hasta que todos los nodos queden con el mismo conjunto, es decir, tengan el mismo representante. Espero que esto aclare tu duda! |
Beta Was this translation helpful? Give feedback.
-
|
Sí, muchas gracias! |
Beta Was this translation helpful? Give feedback.
Para verificar que una arista no forme un ciclo en el árbol, Kruskal utiliza conjuntos disjuntos, donde si los nodos de la arista a verificar están en conjuntos distintos (es decir, ambos tienen un distinto representante), considerar esta arista no forma un ciclo, por lo que si se agrega al árbol y los nodos de la arista pasan a pertenecer al mismo conjunto, en caso contrario la arista forma un ciclo, entonces no se considera.
Entonces para implementar esa lógica, al principio hacemos MakeSet(v) en todos los nodos del grafo original, lo que significa que cada nodo lo estas considerando como un conjunto, donde el mismo nodo es el representante del conjunto, y a medida que va iterando el al…