拓扑排序

拓扑排序算法用于处理在众多复杂的并且相互依赖的事物中寻找一个执行顺序的问题，拓扑算法在日常生活中也是有非常重的应用，例如软件开发、教学安排、生产流程等

• 算法分析：
  拓扑算法的思想是，首先将所有的入度为0（入度表示该点作为终点的边的条数）放入到一个队列中，然后依次从这个队列中取出点，将这个点加入到结果数组中，同时将该点的相关边连接到的点的入度减去1，在这个过程中，如果发现有被处理的点的入度被减到为0，那么就将这个点加入到入度的队列中去。一直进行这个过程，直到入度队列中没有点为止。
• 算法具体代码：

class ENode
{
public:
    int index;          // 该边所指向的顶点的位置
    ENode *nextEdge;    // 指向下一条弧的指针
};
class VNode
{
public:
    char data;          // 顶点信息
    ENode *firstEdge;   // 指向第一条依附该顶点的弧（存储图采用邻接链表的形式）
};
int mVexNum;             // 图的顶点的数目
VNode *mVexs;            // 图的顶点数组
int topologicalSort()
{
    int i,j;
    int index = 0;
    int head = 0;           // 辅助队列的头
    int rear = 0;           // 辅助队列的尾
    int *queue;             // 辅组队列
    int *indegrees;         // 入度数组
    char *results;          // 拓扑排序结果数组，记录为节点具体数据。
    ENode *node;
    
    indegrees   = new int[mVexNum];
    queue = new int[mVexNum];
    results  = new char[mVexNum];
    memset(indegrees, 0, mVexNum*sizeof(int));
    memset(queue, 0, mVexNum*sizeof(int));
    memset(results, 0, mVexNum*sizeof(char));
    
    // 统计每个顶点的入度数
    for(i = 0; i < mVexNum; i++)
    {
        node = mVexs[i].firstEdge;
        while (node != NULL)
        {
            indegrees[node->index]++;
            node = node->nextEdge;
        }
    }
    // 将所有入度为0的顶点入队列
    for(i = 0; i < mVexNum; i ++) {
        if(indegrees[i] == 0)
            queue[rear++] = i; // 入队列
    }
    while (head != rear)                // 队列非空
    {
        j = queue[head++];              // 出队列,j是顶点的序号
        results[index++] = mVexs[j].data;  // 将该顶点添加到tops中，tops是排序结果
        node = mVexs[j].firstEdge;      // 获取以该顶点为起点的出边队列
        
        // 将与"node"关联的节点的入度减1；
        // 若减1之后，该节点的入度为0，则将该节点添加到队列中。
        while(node != NULL)
        {
            // 将节点(序号为node->ivex)的入度减1。
            indegrees[node->index]--;
            // 若节点的入度为0，则将其"入队列"
            if( indegrees[node->index] == 0)
                queue[rear++] = node->index;  // 入队列
            
            node = node->nextEdge;
        }
    }
    if(index != mVexNum)
    {
        cout << "Graph has a cycle" << endl;
        delete queue;
        delete indegrees;
        delete results;
        return 1;
    }
    return 0;
}

• 算法的细节分析：
  算法中使用到了三个数组：
  • indegrees [ ]：用于存储每个顶点的入度
  • queue [ ]：辅助队列，将所有入度为0的节点都放入到这个队列中，然后以队列是否为空为终止条件进行循环处理
  • results [ ]：用于存储最后的排序结果