图 - 拓扑排序 & 关键路径

拓扑排序

AOV网

DAG图：有向无环图
AOV（Activities On Vertex Network）网：用顶点表示活动，用弧表示活动间的优先关系的网.AOV网中不会出现自环（有向环），这意味着有的活动以他自己为前提。

拓扑排序

按照优先顺序对AOV网中的顶点进行排序使之形成一个线性序列。

算法步骤

选择一个无前驱结点并输出；
删除这个结点和所有以其为尾的弧；
重复上述两步直至不存在无前驱结点。此时如果已输出的顶点数小于图中顶点数，说明图中存在自环，否则输出的顶点序列就是一个拓扑序列。

辅助数据结构

一维数组indegree[i]
删除顶点及以其为尾的弧时，不用调整图的存储结构，只需要将弧头结点的入度减1.
栈s
暂存所有入度为0的顶点，避免重复扫描。
一维数组topo[i]
记录拓扑序列的顶点序号。

算法实现

void TopologicalSort(ALGraph G, int topo[]) {
    FindInDegree(G, indegree); // 求各顶点初始化入度
    for(int i = 0; i < G.vexnum; i++)
        if(!indegree[i]) s.push(i); // 暂存入度为0的
    int cnt = 0; // 记录输出的顶点个数
    while(!s.isEmpty()) {
        s.pop(); topo[cnt] = i; cnt++;
        p = G.vertices[i].firstarc; // 第一条依附该结点的边 指向第一个邻接点
        while(p != NULL) {
            k = p->adjvex; indegree[k]--; // 每个邻接点入度减1
            if(!indegree[k]) s.push(k);
            p = p->agjvex; // 指向下一条边
        }
    }
}