• ±â°ü¼Ò°³.
  • µ¶Çлç¶õ
  • ±³¼öÁø¼Ò°³
  • ÇÐÁ¡ÀºÇàÁ¦¶õ
  • ¸í¿¹ÀÇÀü´ç
  • ³ªÀǰ­ÀǽÇ
  • °í°´Áö¿ø¼¾ÅÍ
  • ±³¾ç20ÇÐÁ¡Ãëµæ
HOME > > ÁúÀÇÀÀ´ä
Á¦¸ñ : ÀڷᱸÁ¶ Á¦12,13°­ ¹× ±³Àç Áú¹®ÀÔ´Ï´Ù.
ÀÛ¼ºÀÚ : ±èÇö±Ô ÀÛ¼ºÀÏ : 2011-08-04 17:47:06

ÀڷᱸÁ¶ Á¦12°­
"Æ®¸®¿ë¾î" ½½¶óÀ̵忡¼­ ´Ü¸»³ëµå(A,B,C,D) ºñ´Ü¸»³ëµå(E,F,G,H,I,J)¶ó°í µÇ¾î Àִµ¥ ´Ü¸»³ëµå(E,F,G,H,I,J), ºñ´Ü¸»³ëµå(A,B,C,D)°¡ ¾Æ´Ñ°¡¿ä?

ÀڷᱸÁ¶ Á¦13°­ Æ®¸®(2)
"¿ì¼±¼øÀ§ Å¥ ±¸Çö ¹æ¹ý" ½½¶óÀ̵忡¼­ Ç¥¿Í ±³Àç p197¿¡ Àִ ǥ¿Í ¾Ë°í¸®Áò Ç¥±â¹ýÀÌ ´Ù¸¨´Ï´Ù. ¾î¶²°ÍÀÌ ¸Â´Â°ÍÀΰ¡¿ä?

±³Àç p226
Prim ¾Ë°í¸®Áò¿¡¼­ "let (u, v) be a least cost edge such that u¡ôTV and v¡ôTV"¸¦ Á» ´õ ÀÚ¼¼ÇÏ°Ô ¼³¸íÇØ ÁÖ½Ç ¼ö ÀÖ³ª¿ä?
Á¦ »ý°¢¿¡´Â
let (near(v), v) be a least cost edge such that near(v)¡ôTV and not v¡ôTV
if (theere is no such edge)
  break;
add v to TV;
add (near(v), v) to TV;
À̶ó°í »ý°¢µË´Ï´Ù.