ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——图【5】活动网络(AOV、AOE) (转)

数据结构学习(C++)——图【5】活动网络(AOV、AOE) (转)

原创 IT综合 作者:amyz 时间:2007-11-16 16:36:41 0 删除 编辑
数据结构学习(C++)——图【5】活动网络(AOV、AOE) (转)[@more@]

这部分是和工程相关的,也就是说,当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;

};

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

template class ActivityNetwork;

template class Link

{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;

}

由于public数据成员out和private数据成员result指向同一个数组,在类的外面可以通过out来得到排序结果,只是不能改变(当然,非要改变const数据也不是没有办法)。下面是测试程序,数据来自殷版:

#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;

}

同样的在类的外面可以通过outCriAct得到结果,是一个const引用。如下的测试程序,数据来自殷版:

#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;

}


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-982647/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7372966