图 - 拓扑排序 & 关键路径

拓扑排序

AOV网

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

拓扑排序

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

算法步骤

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

辅助数据结构

1. 一维数组indegree[i]
   删除顶点及以其为尾的弧时，不用调整图的存储结构，只需要将弧头结点的入度减1.
2. 栈s
   暂存所有入度为0的顶点，避免重复扫描。
3. 一维数组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; // 指向下一条边
        }
    }
}

算法分析

求各顶点入度：O(e) + 建立零入度顶点栈O(n) = O(n + e)

关键路径

AOV网

1. AOV（Activity On Edge）网，用边表示活动，顶点表示事件，权值表示活动持续时间的带权有向无环图。
2. 一些定义

• 源点：（唯一的）入度为0的点
• 汇点：（唯一的）出度为0的点
• 带权路径长度：一条路上的权值和
• 关键路径：长度最长的路径（可能不只一条）
• 关键活动：关键路径上的活动，对整个工程时间影响最大

求解过程

1. 对顶点进行排序，用拓扑排序算法求出每个事件的最早发生时间；
2. 逆拓扑排序求出每个事件的最迟发生时间；
3. 求每个活动的最早开始时间和最晚开始时间；
4. 最早开始时间等于最晚开始时间的活动就是关键活动。

算法分析

时间复杂度为O(n + e)