๋ชฉ์ฐจ Spanning Tree ๊ฐ๋ MST(์ต์ ์ ์ฅ ํธ๋ฆฌ) ๊ฐ๋ Prim's Algorithm Kruskal's Algorithm Spanning Tree (์ ์ฅ ํธ๋ฆฌ) ๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ๋ค์ ํฌํจํ๋ ๊ทธ๋ํ์ ๋ถ๋ถ์งํฉ(subgraph) Tree ์ต์ํ์ ๊ฐ์ ๋ค๋ก ๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ์ ํฌํจ - ๋ฐ๋ผ์ Spanning Tree๋ cycle์ ํฌํจํ์ง ์์ - ๊ทธ๋ํ ๋ด์ ์ ์ ์ ์๊ฐ n๊ฐ์ด๋ฉด, Spanning Tree๋ (n-1) ๊ฐ์ ๊ฐ์ ์ ๊ฐ์ง ํ ๊ทธ๋ํ ๋ด์ ์ฌ๋ฌ ๊ฐ์ Spanning Tree๊ฐ ์์ ์ ์์ MST (Minimum Spanning Tree, ์ต์ ์ ์ฅ ํธ๋ฆฌ) ๊ฐ์ค์น๊ฐ ์๋ ๊ทธ๋ํ(weighted graph)์์ ์ต์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง Spanning Tree ์ฆ, ํ ๊ทธ๋ํ ๋ด..
