六讲贯通C++图的应用之六 活动网络(AOV、AOE)(1)

笔者从基本储存方法、DFS和BFS、无向图、最小生成树、最短路径以及活动网络(AOV、AOE)六个方面详细介绍C++图的应用。我们已经前面的文章介绍了前五个方面的知识，今天我们介绍最后一个――活动网络(AOV、AOE)。

活动网络(AOV、AOE)

这部分是和工程相关的，也就是说，当AOV、AOE很复杂的时候，才能显示出这部分的价值――简单的话，手工都要比程序快，输入数据那段时间手工结果就出来了。我也没什么例子好举，总给我一种没底气的感觉，勉为其难的把程序写完就算完事吧。和前边的相比，这部分专业了一点，换而言之，不是每个人都感兴趣，不想看就跳过去吧。

准备工作

活动网络主要有两个算法，拓扑排序和求关键路径，后者以前者为基础。仿照上篇，另外构造一个“算法类”，需要算法时，将图绑定到算法上。

#include "Network.h"   
#define iterator list::edge>::iterator   
#define begin(i) G->data.vertices[i].e->begin()   
#define end(i) G->data.vertices[i].e->end()   
struct CriAct   
{   
CriAct() {}   
CriAct(int source, int dest) : s(source), d(dest) {}   
int s, d;   
};   
template <class name, class dist>   
class ActivityNetwork   
{   
public:   
ActivityNetwork(Network >* G) : G(G), N(G->vNum()), outCriAct(CA)   
{   
count = new int[N]; result = new int[N];   
}   
~ActivityNetwork()   
{   
delete []count; delete []result;   
}   
const vector& outCriAct;   
const int* out;   
private:   
void initialize()   
{   
for (int j = 0; j < N; j++) count[j] = 0;   
for (int i = 0; i < N; i++)   
{   
for (iterator iter = begin(i); iter != end(i); iter++) count[iter->vID]++;   
}   
out = result;   
}   
Network >* G;   
vector CA;   
int N, *count, *result;   
};  

因为AOV和AOE的边都不会太多(想象一下边多的情况，那事件就都是鸡毛蒜皮了)，所以储存结构直接选择了邻接表。并且为了体现邻接表的优势，需要直接操作私有数据，因此要把这个类声明为Link类和Network类的友元，另外由于这个类在后面，所以需要前视声明。具体如下：

template <class name, class dist> class ActivityNetwork;   
template <class name, class dist> class Link   
{friend class ActivityNetwork;};   
template <class name, class dist, class mem> class Network   
{ friend class ActivityNetwork;};