六讲贯通C++图的应用之六活动网络(AOV、AOE)("C++图应用全解析第六讲：活动网络（AOV、AOE）深度探讨")

原创

ithorizon 7个月前 (10-20) 阅读数 31 #后端开发

C++图应用全解析第六讲：活动网络（AOV、AOE）深度探讨

一、引言

在C++图的应用中，活动网络（Activity-On-Vertex，AOV）和活动网络（Activity-On-Edge，AOE）是两种常见的网络模型，用于解决实际问题中的调度和资源分配问题。本讲将深入探讨这两种网络模型的概念、应用以及C++实现方法。

二、AOV网络（活动在顶点上的网络）

AOV网络是一种以顶点描述活动，边描述活动之间先后关系的有向图。在AOV网络中，每个活动都是图中的一个顶点，如果活动A必须在进行活动B之前完成，则在顶点A和顶点B之间有一条有向边。

2.1 AOV网络的应用场景

AOV网络广泛应用于工程项目的进度管理、课程安排、任务调度等领域。例如，在软件开发项目中，可以用来描述各个任务的执行顺序，确保任务之间的依赖性关系得到满足。

2.2 AOV网络的C++实现

以下是使用C++实现AOV网络的一个易懂示例：


#include 
#include 
#include 
using namespace std;
// 定义顶点结构
struct Vertex {
    char data;
    int inDegree; // 入度
};
// 定义边结构
struct Edge {
    int from;
    int to;
};
// 创建图
void createGraph(vector& vertices, vector& edges) {
    // 添加顶点和边
    // 示例代码，具体实现选用实际情况
}
// 计算顶点的入度
void calculateInDegree(const vector& vertices, vector& inDegree) {
    for (const auto& vertex : vertices) {
        inDegree[vertex.data] = vertex.inDegree;
    }
}
// 拓扑排序
void topologicalSort(const vector& vertices, const vector& edges) {
    vector inDegree(256, 0); // 假设顶点数据为ASCII字符
    calculateInDegree(vertices, inDegree);
    queue q;
    for (const auto& vertex : vertices) {
        if (inDegree[vertex.data] == 0) {
            q.push(vertex.data);
        }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        cout << v << " ";
        for (const auto& edge : edges) {
            if (edge.from == v) {
                inDegree[edge.to]--;
                if (inDegree[edge.to] == 0) {
                    q.push(edge.to);
                }
            }
        }
    }
}
int main() {
    vector vertices;
    vector edges;
    createGraph(vertices, edges);
    topologicalSort(vertices, edges);
    return 0;
}

三、AOE网络（活动在边上的网络）

AOE网络是一种以边描述活动，顶点描述事件的有向图。在AOE网络中，每个活动都是一条边，如果活动A必须在进行活动B之前完成，则有一条从事件A到事件B的边。

3.1 AOE网络的应用场景

AOE网络常用于描述工程项目的进度和资源分配，通过计算关键路径和关键活动，可以找出影响项目完成的关键因素，从而优化项目进度。

3.2 AOE网络的C++实现

以下是使用C++实现AOE网络的一个易懂示例：


#include 
#include 
#include 
#include 
using namespace std;
// 定义顶点结构
struct Vertex {
    int data;
    int inDegree; // 入度
};
// 定义边结构
struct Edge {
    int from;
    int to;
    int weight; // 权重，描述活动持续时间
};
// 创建图
void createGraph(vector& vertices, vector& edges) {
    // 添加顶点和边
    // 示例代码，具体实现选用实际情况
}
// 计算顶点的入度
void calculateInDegree(const vector& vertices, vector& inDegree) {
    for (const auto& vertex : vertices) {
        inDegree[vertex.data] = vertex.inDegree;
    }
}
// 计算关键路径
void criticalPath(const vector& vertices, const vector& edges) {
    vector inDegree(256, 0); // 假设顶点数据为ASCII字符
    vector earliest(256, 0); // 最早起初时间
    vector latest(256, INT_MAX); // 最迟起初时间
    calculateInDegree(vertices, inDegree);
    queue q;
    for (const auto& vertex : vertices) {
        if (inDegree[vertex.data] == 0) {
            q.push(vertex.data);
            earliest[vertex.data] = 0;
        }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (const auto& edge : edges) {
            if (edge.from == v) {
                inDegree[edge.to]--;
                if (inDegree[edge.to] == 0) {
                    q.push(edge.to);
                }
                earliest[edge.to] = max(earliest[edge.to], earliest[v] + edge.weight);
            }
        }
    }
    // 计算最迟起初时间
    for (int i = 255; i >= 0; i--) {
        for (const auto& edge : edges) {
            if (edge.to == i) {
                latest[edge.from] = min(latest[edge.from], latest[edge.to] - edge.weight);
            }
        }
    }
    // 输出关键路径
    for (const auto& edge : edges) {
        if (earliest[edge.from] == latest[edge.from] && earliest[edge.to] == latest[edge.to]) {
            cout << edge.from << " -> " << edge.to << " (关键活动)" << endl;
        }
    }
}
int main() {
    vector vertices;
    vector edges;
    createGraph(vertices, edges);
    criticalPath(vertices, edges);
    return 0;
}