https://www.geeksforgeeks.org/what-is-minimum-spanning-tree-mst/
What is Minimum Spanning Tree (MST) - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
์ ์ฅ ํธ๋ฆฌ(Spanning Tree)๋?
์ ์ฅ ํธ๋ฆฌ๋ ๋ชจ๋ ๋ ธ๋๊ฐ ํธ๋ฆฌ์ ์ผ๋ถ์ธ ๋น์ํ ํธ๋ฆฌ๋ฅผ ํ์ฑํ๋ ๊ทธ๋ํ์ ๊ฐ์ ์ ๋ถ๋ถ ์งํฉ์ด๋ค.
์ ์ฅ ํธ๋ฆฌ ํน์ฑ
- ๊ทธ๋ํ์ ์ก์ ํธ๋ฆฌ์ ์ ์ ์ ์๋ ๊ฐ๋ค.
- ์ ์ฅ ํธ๋ฆฌ์๋ ์ ์ ์ ์ด ๊ฐ์๋ณด๋ค ํ๋ ์ ์ ๊ณ ์ ๋ ๊ฐ์์ ๊ฐ์ ์ด ์๋ค.
- ์ ์ฅ ํธ๋ฆฌ๋ ๋ถ๋ฆฌ๋์ด์๋ ์ ๋๋ค.
- ์ ์ฅ ํธ๋ฆฌ๋ ์ฌ์ดํด์ด ์์ด์ผ ํ๋ค.
- ์ ์ฅ ํธ๋ฆฌ์ ์ด ๋น์ฉ์ ์ ์ฅ ํธ๋ฆฌ์ ๋ชจ๋ ๊ฐ์ ์ ๊ฐ์ค์น์ ํฉ์ด๋ค.
- ๊ทธ๋ํ์๋ ์ฌ๋ฌ ๊ฐ์ ์ ์ฅ ํธ๋ฆฌ๊ฐ ์์ ์ ์๋ค.
์ต์ ์ ์ฅ ํธ๋ฆฌ(Minimum Spanning Tree, MST)๋?
์ต์ ์ ์ฅ ํธ๋ฆฌ๋ ๊ฐ๋ฅํ ๋ชจ๋ ์ ์ฅ ํธ๋ฆฌ ์ค ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๋งํ๋ค. ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ ๊ฐ๋ฅํ ๋ชจ๋ ์ ์ฅ ํธ๋ฆฌ ์ค ๊ฐ๋ฅํ ๊ฐ์ฅ ์ต์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง๋ค๋ ์ ์ฝ์ด ์์ผ๋ฉฐ, ๋ชจ๋ ์ ์ฅ ํธ๋ฆฌ์ ํน์ฑ์ ๊ฐ์ง๋ค.
์ ์ฅ ํธ๋ฆฌ์ ๊ฐ์ด ๊ทธ๋ํ์ ๋ํ ๊ฐ๋ฅํ MST๋ ์ฌ๋ฌ ๊ฐ๊ฐ ์์ ์ ์๋ค.
ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ(Kruskal's Algorithm)
์ฐ๊ฒฐ๋ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์์ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ๋ ๋ฐ ๋๋ฆฌ ์ฐ์ด๋ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋์ด๋ฉฐ, ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy algorithm)์ด๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ด ์ํํ๋ค.
- ๊ฐ์ค์น์ ๋ํด ๊ทธ๋ํ์ ๊ฐ์ ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค.
- ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ์ผ๋ฉฐ ๋ฐ๋ณตํ๋ค.
- ๊ฐ์ฅ ์์ ๊ฐ์ค์น์ ๊ฐ์ ์ ์ถ๊ฐํด์ ์ํ์ ํ์ฑํ์ง ์์ ๋๊น์ง ๊ฐ์ ์ ์ ํํ๋ค.
๊ทธ๋ํ์ ์ฐ๊ฒฐ๋ ๊ตฌ์ฑ ์์๋ฅผ ์ถ์ ํ๊ธฐ ์ํด Disjoint-SET ์๋ฃ ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ์ฌ ํจ์จ์ ์ผ๋ก ๊ตฌํํ ์ ์๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ๋คํธ์ํฌ ์ค๊ณ, ํด๋ฌ์คํฐ๋ง, ๋ฐ์ดํฐ ๋ถ์๊ณผ ๊ฐ์ ๋ค์ํ ์ค์ฉ์ ์ธ ์์ฉ ๋ถ์ผ์ ์ฌ์ฉ๋๋ค.
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ(Prim's Algorithm)
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ๋ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ์ฐ๊ฒฐ๋ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์์ ์ฌ์ฉํ๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ด ์ํํ๋ค.
- ์์์ ์ ์ ์ ์ ํํ์ฌ ์์ํ๊ณ MST์ ์ด๋ฅผ ์ถ๊ฐํ๋ค.
- MST์ ํ๋์ ์ ์ ๊ณผ ์์ง MST์ ์๋ ์ ์ ์ ์ฐ๊ฒฐํ๋ ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ ๊ฐ์ ์ ๋ฐ๋ณต์ ์ผ๋ก ํ์ธํ๋ค.
- MST์ ๋ชจ๋ ์ ์ ์ด ํฌํจ๋ ๋๊น์ง ์ ๊ณผ์ ์ ๊ณ์ํ๋ค.
๊ฐ ๋ฐ๋ณต์ ๋ํ ๊ฐ์ฅ ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ ๊ฐ์ ์ ํจ์จ์ ์ผ๋ก ์ ํํ๊ธฐ ์ํด ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค. ๋ํ ๋์์ ์ ์ฅํ๋ ๋ฐ์ดํฐ ํ์ ์ ๊ณ ๋ คํ ๋ ์ ํฉํ ๋ค๋ฅธ ์๋ฃ ๊ตฌ์กฐ๋ ๋ฐฐ์ด์ ์ฌ์ฉํ์ฌ MST๋ฅผ ์ถ์ ํ๋ค.