- ½ÅÀåÆ®¸® : ±×·¡ÇÁ G¿¡
ÀÖ´Â ¸ðµç Á¤Á¡°ú ±× Á¤Á¡µéÀ»
¿¬°áÇÏ´Â °£¼±À¸·Î ±¸¼ºµÈ
Æ®¸®
- ÃÖ¼Ò ½ÅÀåÆ®¸® : °¡ÁßÄ¡°¡
ÀÖ´Â ±×·¡ÇÁ G¿¡¼ ÃÖ¼Ò °¡ÁßÄ¡·Î
±¸¼ºµÈ ½ÅÀåÆ®¸®, KruskalÀÇ
¾Ë°í¸®Áò°ú PrimÀÇ ¾Ë°í¸®Áò
- PrimÀÇ ¾Ë°í¸®Áò
: Dijkstra ¾Ë°í¸®Áò°ú
À¯»çÇϳª PrimÀÇ ¾Ë°í¸®ÁòÀº
·çÆ®¿¡¼ ½ÃÀÛÇÏÁö ¾Ê°í
ÇöÀç±îÁö ¿Ï¼ºµÈ Æ®¸®ÀÇ
°¢ ³ëµå¿¡¼ ÀÎÁ¢ÇÑ Á¤Á¡»çÀÌÀÇ
°ªÀÌ °¡Àå ÀÛÀº Á¤Á¡À»
Æ®¸®·Î Èí¼öÇÑ´Ù. »çÀÌŬ
Á¦¿ÜÇÔ.
- KruskalÀÇ ¾Ë°í¸®Áò
: ¸ðµç °£¼±µéÀÇ ºñ¿ëÀ»
¿À¸§Â÷¼øÀ¸·Î Á¤·ÄÇÏ°í
ºñ¿ëÀÌ ÀûÀº °ÍºÎÅÍ ¼øÂ÷·Î
¼±ÅÃÇϵÇ, »çÀÌŬÀÌ ¹ß»ýÇÏ´Â
°£¼± Á¦¿Ü
|
*
Prim ÀÇ ¾Ë°í¸®ÁòÀ̳ª KruskalÀÇ ¾Ë°í¸®Áò
¸ðµÎ °°Àº °á°ú¸¦ °¡Á®¿Â´Ù. PrimÀÇ ¾Ë°í¸®ÁòÀº
Dijkstra(´ÙÀͽºÆ®¶ó)ÀÇ ¾Ë°í¸®Áò°ú
°°ÀÌ ÇÑ ³ëµå¿¡¼ Ãâ¹ßÇÏ¿© ÃÖ¼Ò½ÅÀå Æ®¸®¸£
±¸Çϳª, Kruskal ÀÇ ¾Ë°í¸®ÁòÀº ¸ðµç °£¼±µéÀÇ
ºñ¿ëÀ» ¿À¸§ Â÷¼øÀ¸·Î
Á¤·ÄÇÏ¿© ÀÛÀº °ÍºÎÅÍ ±×·Á ³ª°¡¹Ç·Î ±¸Çϱâ
½±´Ù.
|