关于算法>贪心算法介绍：
http://blog.csdn.net/mind_v/article/details/72956707

拓扑排序">拓扑排序

问题描述

一个复杂的工程，经常可以分解成一组简单一些的任务，这些任务完成了，整个工程就完成了。例如汽车组装问题可以分解成：底盘安装、车轴安装、车轮安装、座位安装、喷漆、刹车安装、车门安装等。但是这些任务之间有个先后顺序，例如车轴安装之前先要进行底盘安装。

类似的问题，可以将任务和人物的先后顺序用有向图表示——称为顶点活动网络，顶点代表一个任务，有向边（i，j）代表任务i要在任务j之前完成。下图就是一个工程，它有6个任务，边（1,3）表示任务1要在任务3开始前完成，边（4,6）表示任务4要在任务6之前完成。

任务有向<a class= 图" title="" />

这样就形成了一个任务序列，对有向图的任意一条边（i，j），在这个序列中，任务i一定出现在任务j之前，具有这种性质的序列叫做拓扑序列（topological order），根据有向图建立拓扑序列的过程称为拓扑排序（topological sorting）。

对于这样一个有向图有若干个拓扑序列，如1-2-3-4-5-6,1-3-2-4-5-6,2-1-3-4-5-6等。

贪心求解

我们可以通过从左到右分步构造拓扑序列，每一步选择一个新顶点加入到序列中。选择新顶点的贪心准则：从剩余的顶点中选择一个顶点w，所有邻接于它的顶点都在序列中。

算法步骤：

令n表示有向图的顶点数
令theOrder表示空虚列
while(true)
{
  令w是任意一个没有入边(v,w)的顶点，其中v不在theOrder中
  如果没有这样的顶点w，算法终止
  把w加入到theOrder的尾部
}
if(theOrder的顶点数小于n)
  算法失败
else
  theOrder是一个拓扑序列

针对上图，使用这样一个算法：
从theOrder是一个空序列开始，第一步选择插入theOrder序列的第一个顶点，顶点1和2都满足贪心准则。若选择1，则theOrder{1}；第二步插入第二个顶点，这时有两个个候选顶点2,3。若选择3，则theOrder{1,3}；第三步选择第三个顶点，候选顶点只有2，则theOrder{1,3,2}；第四步候选顶点为4和5，如果选择4，则theOrder{1,3,2,4}；第五步只有一个候选顶点5，第六步最后一个顶点6，则theOrder{1,3,2,4,5,6}。

数据结构选择：
用一个一维数组表示theOrder，存储拓扑序列；用一个栈存储可以加入theOrder的候选顶点；用一个一维数组inDegree存储每个顶点的实时入度，inDegree[j]表示不在theOrder中但邻接于顶点j的数目。每次向theOrder中添加,一个顶点时，所有邻接于此顶点的顶点j，theDegree[j]减1，当inDegree变成0时，表示顶点j成为候选顶点。

C++实现

函数是图的graph抽象类的成员函数，使用到的接口包括：
directed()：确定图是否是有向图
numberOfVertices()：返回图的顶点数
vertexIterator类：创造一个顶点的迭代器，其next()成员返回邻接于改顶点的下一个顶点。

arrayStack是用数组描述的栈，接口：
push(i)：将i压入栈
pop()，删除栈顶元素

bool topologicalOrder(int *theOrder)
{//返回false，当且仅当有向图没有拓扑序列
 //如果存在一个拓扑序列，则将顶点赋给theOrder[0,n-1]

    //确定是有向图
    if (!directed())
        return;

    int n = numberOfVertices();

    //计算入度
    int *inDegree = new int[n + 1];
    fill(inDegree + 1, inDegree + n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        vertexIterator<int> *ii = iterator(i);
        int u;
        if ((u = ii->next()) != 0)
            inDegree[u]++;
    }

    //把入边数加入到栈中
    arrayStack<int> stack;
    for (int i = 1; i <= n; ++i)
        if (inDegree[i] == 0)
            stack.push(i);

    //生成拓扑序列
    int j = 0;
    while (!stack.empty())
    {
        int theVertex = stack.top();
        stack.pop();
        theOrder[j++] = theVertex;
        //更新入边数
        vertexIterator<int> *iTheVertex = iterator(theVertex);
        int u;
        while ((u = iTheVertex->next()) != 0)
        {
            inDegree[u]--;
            if (inDegree[u] == 0)
                stack.push(u);
        }
    }
    return (j == n);
}