๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Prim1

[MST] ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ - ํฌ๋ฃจ์Šค์นผ(Kruskal), ํ”„๋ฆผ(Prim) MST๋ž€? ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(Minimum Spanning Tree)๋กœ ๊ฐ€์ค‘ ๊ทธ๋ž˜ํ”„(Weight Graph)์—์„œ ๊ฐ€์žฅ ์ ์€ ๋น„์šฉ(Weight)์œผ๋กœ ๋ชจ๋“  ์ •์ (Vertex)์œผ๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋ถ€๋ถ„ ๊ทธ๋ž˜ํ”„(Sub Graph)์ด๋‹ค. MST๋Š” ๊ฐ ์ •์ ์—์„œ ์ •์  ์‚ฌ์ด์— ํ•˜๋‚˜์˜ ๊ฐ„์„ (Edge)๋งŒ ํ•„์š”ํ•˜๋ฏ€๋กœ ์ด N-1 ๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฐ€์ง€๊ฒŒ ๋˜๋ฏ€๋กœ ๋งˆ์น˜ ํŠธ๋ฆฌ์˜ ํ˜•ํƒœ๋ฅผ ํ•˜๊ณ  ์žˆ์–ด์„œ ํŠธ๋ฆฌ๋ผ๋Š” ์ด๋ฆ„์ด ๋ถ™๋Š”๋‹ค.ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ 1. ๋ชจ๋“  ๊ฐ„์„ ์„ ๋น„์šฉ์ด ์ ์€ ์ˆœ์„œ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค. - Sort2. ๊ฐ„์„ ์— ๋ถ™์€ ์ •์  u์™€ v๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ถ€๋ชจ๋ฅผ ์ฐพ๋Š”๋‹ค. - Find3. ์ •์  u์˜ ๋ถ€๋ชจ์™€ ์ •์  v์˜ ๋ถ€๋ชจ๊ฐ€ ๋‹ค๋ฅด๋‹ค๋ฉด ์„œ๋กœ ๋‹ค๋ฅธ ์ง‘ํ•ฉ์— ์†ํ•ด์žˆ์ง€๋งŒ, 1๋ฒˆ ๊ณผ์ •์œผ๋กœ ์ธํ•ด ํ•ด๋‹น ๊ฐ„์„ ์ด ๋‘ ์ •์ ์˜ ์ตœ์†Œ ๋น„์šฉ์˜ ๊ฐ„์„ ์ž„์„ ์•Œ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ํ•˜๋‚˜์˜.. 2024. 7. 11.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”