《Algorithms》第5章：Greedy Algorithms 学习笔记
Chapter 5：Greedy Algorithms
1、Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
2、每步只看眼前效果最好的做法就是贪婪，我们希望通过局部最优达到全局最优。贪婪算法只找到一种可行解，但不一定是最优解。
3、最小生成树性质一：Removing a cycle edge can not disconnect a graph性质二：A tree on n nodes has n-1 edges.
树是连通且没有环的无向图。树因为其结构的简单性而具有很多应用。例如，n个结点的树有且仅有n-1条边。n个结点和n-1条边构成的图不一定是树，但如果此图是连通的，则一定是树性质三：Any connected, undirected graph G = (V, E) with |E| = |V| - 1 is a tree.性质四：An undirected graph is a tree if and only if there is a unique path between any pair of nodes.
4、割性质（Kruskal和prim算法的基础）：假定边集X是图G = (V, E)的某个最小生成树的一部分。在图G中挑选任意一组结点S，使得X里没有边横跨S和V-S两个结点集合。假如e是所有横跨这两个集合权重最小的，则X∪{e}是某个最小生成树的一部分。
5、最小生成树的算法Kruskal算法
