Minimum Spanning Tree
Need to connect all nodes to the tree in the smallest possible way
1, ๋ง๋๋ ๋ฒ
Kruskal’s algorithm์ ๋ฐ๋ผ์ ๋ง๋ ๋ค. (์์ธํ ์์๋ ์ฐธ๊ณ ์ฌ์ดํธ[1] ์ฐธ๊ณ ํ๊ธฐ)
2. ๊ท์น ๋ฐ ํน์ง
๊ท์น1. Check each node is connected and no breaks in the tree.
๊ท์น2. Don’t add an edge if it doesn’t improve connectivity.
ํน์ง1. There may be more than one MST.
์ฐธ๊ณ ์ฌ์ดํธ
[1] Youtube