目錄
最小生成樹算法
1、Kruskal
1.1 算法簡介
1.2 C++實作
最小樹定義：
給定網絡\(G=(N,E,W)\)，設\(T=(N,E')\)為\(G\)的一個支撐樹，令\(W(T)=\sum_{e\in E'}W(e)\)為\(T\)的權（或長）。\(G\)中權最小的支撐樹稱為\(G\)的最小樹。
并查集:用一個元素代表一組元素，用于查詢不同元素是否屬于同一組，以及合并組
Kruskal是1956年首次提出的求最小生成樹的算法，後來Edmonds把該算法稱為貪心算法，其基本思路就是從G中的m條邊中選取n-1條權盡可能小的邊，使其不構成回路，進而構成一個最小樹。
第一步：把圖按照邊權的大小從小到大排列起來，初始化一個已選中的邊集，或計數器
第二步：不斷從加入之後不構成環的邊中選擇權最小的邊加入邊集
第三步：如果邊集中邊的數量達到n-1，則停止，否則繼續選邊加邊
祝看到這裡的你生活愉快，謝謝