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

ํฌ๋ฃจ์Šค์นผ

(1)
[Java] Kruskal's Algorithm ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST) ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ MST(Minimun Spanning Tree) - ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž๋ฐ” ๊ตฌํ˜„ ๐Ÿง ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ MST(Minimun Spanning Tree)๋ž€? ์ตœ์†Œํ•œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ์ •์ ์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์„ ์ˆ˜ ์žˆ๊ฒŒํ•˜๋Š” ๊ธฐ๋ฒ•์ด๋‹ค. ์˜ˆ์‹œ) ๋„์‹œ๋“ค์€ ๋ชจ๋‘ ๋‹ค๋ฆฌ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ์„ ๋•Œ, ๋ชจ๋“  ๋„์‹œ๋ฅผ ๊ฐˆ ์ˆ˜ ์žˆ๊ฒŒ ๋‹ค๋ฆฌ๋ฅผ ์—ฐ๊ฒฐํ•˜๋˜ ์ตœ์†Œํ•œ์˜ ๋‹ค๋ฆฌ ๊ธธ์ด๋งŒ์„ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ๋ฒ• (๋„์‹œ๊ฐ€ ๊ฐ€๋กœ๋“ฑ์œผ๋กœ ๋‹ค๋ฆฌ๊ฐ€ ์ „์„ ์œผ๋กœ ๋ฐ”๋€”์ˆ˜๋„ ์žˆ๋‹ค.) ๋„ค๋น„๊ฒŒ์ด์…˜์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ชจ๋“  ์ •์ (node ํ˜น์€ vortex)๊ฐ€ ์—ฐ๊ฒฐ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ๋กœ ์ค‘ ๊ฐ€์žฅ ์ ์€ ๊ฐ€์ค‘์น˜(์—ฌ๊ธฐ์„  ๊ฑฐ๋ฆฌ)๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ๋กœ ์ฃผ์˜์‚ฌํ•ญ ์—ฌ๊ธฐ์„œ ์—ฐ๊ฒฐ์ด๋ž€ ๋‹ค๋ฅธ ๋…ธ๋“œ๋ฅผ ๊ฑฐ์ณ์„œ ๊ฐ€๋Š” ๊ฒƒ์„ ํฌํ•จํ•œ๋‹ค. ๊ฐ„์„  ํ˜น์€ ๋ธŒ๋žœ์น˜(๋…ธ๋“œ๋ฅผ ์ด์–ด์ฃผ๋Š” ์„ , ๊ฑฐ๋ฆฌ)๋Š” ๋ฐฉํ–ฅ์„ฑ์„ ๊ฐ–์ง€ ์•Š๋Š”๋‹ค.(์—ฐ๊ฒฐ๋งŒ ๋˜์–ด์žˆ..

728x90