贪婪算法
算法思想:在贪婪算法(greedy method)中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就不可再更改。作出贪婪决策的依据称为贪婪准则(greedy criterion)。
拓扑排序:
1. 算法描述:
设n是有向图中的顶点数,设V是一个空序列
w h i l e(t ru e)
{
设w不存在入边( v,w),其中顶点v不在V中
如果没有这样的w,b re a
k。
把w添加到V的尾部
}
i f(V中的顶点数少于n) //算法失败
{
else V是一个拓扑序列
}
2. 代码示例: