# 数据结构学习（C++）——图【5】活动网络（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 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;

};

template class ActivityNetwork;

{friend class ActivityNetwork;};

template class Network

{ friend class ActivityNetwork;};

### 拓扑排序

bool TopoSort()

{

initialize(); int i, top = -1;

for (i = 0; i < N; i++) if (!count[i]) { count[i] = top; top = i; }

for (i = 0; i < N; i++) //TopoSort StartXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

{

if (top == -1) return false;

result[i] = top; top = count[top];

for (iterator iter = begin(result[i]); iter != end(result[i]); iter++)

if (!--count[iter->vID]) { count[iter->vID] = top; top = iter->vID; }

}

return true;

}

#include

using namespace std;

#include "ActivityNetwork.h"

int main()

{

Network > a;

a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);a.insertV(5);

a.insertE(0,3,1);a.insertE(0,1,1);a.insertE(1,5,1);a.insertE(2,1,1);

a.insertE(2,5,1);a.insertE(4,0,1);a.insertE(4,1,1);a.insertE(4,5,1);

ActivityNetwork b(&a);

if (b.TopoSort()) for (int i = 0; i < a.vNum(); i++) cout << b.out[i] << ' ';

return 0;

}

### 关键路径

bool CriPath()

{

if (!TopoSort()) return false; int i; iterator iter; CA.clear();

dist* Ve = new dist[N]; dist* Vl = new dist[N];//Ve最早开始时间，Vl最迟开始时间

for (i = 0; i < N; i++) Ve[i] = 0;//Ve初始化

for (i = 0; i < N; i++)//按拓扑顺序计算Ve

for (iter = begin(result[i]); iter != end(result[i]); iter++)

if (Ve[result[i]]+iter->cost>Ve[iter->vID]) Ve[iter->vID]= Ve[result[i]] + iter->cost;

for (i = 0; i < N; i++) Vl[i] = Ve[N - 1];//Vl初始化

for (i = N - 2; i >= 0; i--)//按逆拓扑顺序计算Vl

for (iter = begin(result[i]); iter != end(result[i]); iter++)

if (Vl[iter->vID]-iter->cost < Vl[result[i]]) Vl[result[i]] = Vl[iter->vID] - iter->cost;

for (i = 0; i < N; i++)//计算各个活动的最早开始时间和最迟开始时间

for (iter = begin(i); iter != end(i); iter++)

if (Ve[i] == Vl[iter->vID] - iter->cost) CA.push_back(CriAct(i, iter->vID));

return true;

}

#include

using namespace std;

#include "ActivityNetwork.h"

int main()

{

Network > a;

a.insertV(0);a.insertV(1);a.insertV(2);a.insertV(3);a.insertV(4);

a.insertV(5); a.insertV(6);a.insertV(7);a.insertV(8);

a.insertE(0,1,6);a.insertE(0,2,4);a.insertE(0,3,5);

a.insertE(1,4,1);a.insertE(2,4,1);a.insertE(3,5,2);

a.insertE(4,6,9);a.insertE(4,7,7);a.insertE(5,7,4);

a.insertE(6,8,2);a.insertE(7,8,4);

ActivityNetwork b(&a);

if (b.CriPath())

for (int j = 0; j < b.outCriAct.size(); j++)

cout <<'<'<' << ' ';

return 0;

}

• 博文量
3984
• 访问量
7372966