图 学习笔记（二）(11.25)

大家好，欢迎来到IT知识分享网。

一、有向无环图及其应用

1.AOV网与拓扑排序

AOV网： 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。
其中弧表示活动之间的制约关系，AOV网不能有回路。
拓扑排序： 参考学习笔记（一）
·”无前驱”顶点优先的另一种实现：
图存储：邻接表，在顶点表中增加入度域；栈：存储所有无前驱的顶点(入度为零的顶点)。

#include<bits/stdc++.h> using namespace std; const int MaxSize = 10; struct EdgeNode//边表结点结构体 { 
    int adjvex;//该顶点的邻接点在顶点表中的下标 EdgeNode *next; }; struct VertexNode//顶点表结点结构体 { 
    int in;//入度 int vertex;//存放顶点信息 EdgeNode *firstEdge;//指向边表的第一个结点 }; class ALGraph { 
    public: ALGraph(int a[], int n, int e); //构造函数，建立n个顶点e条边的图 ~ALGraph(); void TopSort(); private: VertexNode adjlist[MaxSize]; //存放顶点表的数组 int vertexNum,edgeNum;//顶点数和边数 }; ALGraph::ALGraph(int a[],int n,int e) { 
    int i,j,k; EdgeNode *s=NULL; vertexNum=n; edgeNum=e; for(i=0; i<vertexNum; i++) //初始化顶点表 { 
    adjlist[i].vertex=a[i]; adjlist[i].firstEdge=NULL; } for(k=0; k<edgeNum; k++) { 
    cin>>i>>j; s=new EdgeNode; s->adjvex=j; s->next=adjlist[i].firstEdge; adjlist[i].firstEdge=s;//头插法 } for(i=0; i<vertexNum; i++) { 
    cin>>adjlist[i].in; } } ALGraph::~ALGraph() { 
    EdgeNode *p=NULL,*q=NULL; for(int i=0; i<vertexNum; i++) { 
    p=q=adjlist[i].firstEdge; while(p!=NULL) { 
    p=p->next; delete q; q=p; } } } void ALGraph::TopSort() { 
    int i,j,k,count=0; int S[MaxSize],top=-1; EdgeNode *p=NULL; for(i=0; i<vertexNum; i++) { 
    if(adjlist[i].in==0) S[++top]=i; } while(top!=-1) { 
    j=S[top--]; cout<<adjlist[j].vertex<<" "; count++; p=adjlist[j].firstEdge; while(p!=NULL) { 
    k=p->adjvex; adjlist[k].in--; if(adjlist[k].in==0) S[++top]=k; p=p->next; } } if(count<vertexNum) cout<<"有回路"; } int main() { 
    int ch[]= { 
   0,1,2,3}; ALGraph ALG(ch,4,4); ALG.TopSort(); return 0; } 

2.AOE网与关键路径

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，这样的有向图叫做边表示活动的网，称为AOE网。
AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。正常的AOE网只有一个始点和一个终点。
AOE网的性质：
⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

某工程如下：

事件的最早发生时间ve[k]

根据性质：只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。顶点最早发生时间取决于前面活动结束最晚的，所以，顶点v_k的最早发生时间ve[k]应该等于前一个顶点max(ve[j]+len<v_j,v_k>)。初始化ve[0]=0;

事件的最迟发生时间vl[k]

vl[k]是指在不推迟整个工期的前提下,事件v_k允许的最晚发生时间。
因为整个工期不能延期，所以vl[n-1]=ve[n-1]，即最后一个事件的最早与最迟发生时间一致才不会延期。这也就是初始化。
所以倒着考虑，根据性质只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始。即在后一项事件v_j，最迟发生时间的基础上减去len<v_k,v_j>即可，又因为事件v_k后面可能有多个活动，为了让持续时间最长的活动也能按期完成，所以vl[k]=min(vl[j]-len<v_k,v_j>)

活动的最早开始时间e[i]

因为活动由<vk , vj>表示，活动的最早开始时间应等于事件v_k的最早发生时间。所以e[i]=ve[k];

活动的最晚开始时间l[i]

根据性质只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。倒推活动的最晚开始时间应该等于后一事件的最晚开始时间-活动持续时间，也就是el[i]=vl[j]-len<v_k,v_j>。这里与事件最晚开始时间的区别是没有min，因为事件会受到多个活动的影响。


关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。
关键活动：关键路径上的活动称为关键活动。


上图标红的路线就是关键路径，关键路径不一定唯一，e[i]=l[i]的活动是关键活动。
注意：任意一个关键活动延期，整个工期会延期（✓）
任意一个关键活动加快，整个工期不一定会加快（✓）可能有多个关键路径
任意一个非关键活动延期，工期一定不会延期（×）因为延期有范围
任意一个非关键活动加快，工期一定不会加快（✓）