一、 贪心策略的定义
【定义1】 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实，从"贪心策略"一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
二、贪心算法的特点
通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
1、贪心选择性质：
所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部最优解：
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。
在遇到具体问题时，往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。
三、 贪心策略的理论基础--矩阵胚
正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论--矩阵胚。
"矩阵胚"理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。
【定义3】 矩阵胚是一个序对M=[S，I] ，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。
如果M是一个N×M的矩阵的话，即:
若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。
如果对S的每一个元素X（X∈S）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。
适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。
矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。
四、 几种典型的贪心算法
贪心策略在图论中有着极其重要的应用。诸如Kruskal、 Prim、 Dijkstra等体现“贪心”思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal算法、Prim算法和Dijkstra算法。
.
Ⅰ、库鲁斯卡尔（Kruskal）算法
【定义4】 设图G=（V，E）是一简单连通图，｜V｜ =n,｜E｜=m,每条边ei都给以权W ，W 假定是边e 的长度（其他的也可以），i=1，2，3，...，m。求图G的总长度最短的树，这就是最短树问题。
kruskal算法的基本思想是：首先将赋权图G的边按权的升序排列，不失一般性为：e ,e ,......,e 。其中W ≤W ，然后在不构成回路的条件下择优取进权最小的边。
其流程如下：
（1） 对属于E的边进行排序得e ≤e ≤...... ≤e 。
（2） 初始化操作 w←0，T←ф ，k←0，t←0；
（3） 若t=n-1，则转（6），否则转（4）
（4） 若T∪｛e ｝构成一回路，则作
【k←k+1，转（4）】
（5） T←T∪{ e }，w←w+ w ，t←t+1，k←k+1，转（3）
（6） 输出T，w，停止。
下面我们对这个算法的合理性进行证明。
设在最短树中，有边〈v ，v 〉，连接两顶点v ，v ，边〈v ，v 〉的权为wp，若〈v ，v 〉加入到树中不能保证树的总长度最短，那么一定有另一条边〈v ，v 〉或另两条边〈v ，v 〉、〈v ，v 〉，且w<vi，vj><wp或w<vi，vk>+w〈vk，vj〉<wp，因为〈v ，v 〉、〈v ，v 〉不在最短树中，可知当〈v ，v 〉、〈v ，v 〉加入到树中时已构成回路，此时程序终止。因为〈v ，v 〉∈ T，〈v ，v 〉∈T且w〈vI，vk〉+w〈vk，vj〉<w p，与程序流程矛盾。
下面给出C语言描述的kruskal算法:
#define MAXE <最多的边数>
typedef struct {
int u;// 边的起始顶点
int v;// 边的终止顶点
int w;// 边的权值
} Edge;
void kruskal(Edge E[],int n,int e)//边的权值从小到大排列
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXV];
for(i=0;i<n;i++)
vset[i]=i;
k=1;j=0;
while(k<n)
{
m1=E[j].u;
m2=E[j].v;
sn1=vset[m1];
sn2=vset[m2];
if(sn1!=sn2)//两顶点属于不同的集合,是最小生成树的一条边
{
输出这条边;
k++;
for(i=0;i<n;i++)
if(vset[i]==sn2)
vset[i]=sn1;
}
j++;
}
}
kruskal算法对边的稀疏图比较合适,时间复杂度为o(elog2e),e是边数,与顶点无关.