拓扑排序
有向无环图DAG
顶点表示活动的网络AOV网：用DAG图表示一个工程，其顶点表示活动，有向边<vi,vj>表示活动vi必须先于活动vj进行
拓扑排序（由一个有向无环图的顶点组成的序列）
1.每个顶点出现且仅出现一次
2.若顶点A在序列中排在顶点B之前，则图中不存在B到A的路径
每个DAG图都有一个或多个拓扑排序序列。
若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序序列中，每个顶点有唯一的前驱后继关系，再做拓扑排序时，则排序结果是唯一的。
若邻接矩阵是三角矩阵的话拓扑排序一定存在，反之不一定。
步骤
1.从DAG图中选择一个没有前驱的顶点并输出（必须在它之前进行大的活动已经都完成了）
2.从图中删除该顶点和所有以它为起点的有向边
3.重复1，2直到当前的DAG图为空或当前图中不存在无前驱的结点为止。后者说明有环。
拓扑排序过程.JPG
队列
void Graph::topsort()
{
Queue<Vertex> q;
int counter=0;
q.makeEmpty();
for each Vertex v
if(v.indegree==0)
q.enqueue(v);
while(!q.isEmpty())
{
Vertex v=q.dequeue();
v.topNum=++counter;
for each Vertex w adjacent to v
if(--w.indegree==0)
q.enqueue(w);
}
if(counter!=NUM_VERTICES)
throw CycleFoundException();
}
栈
bool TopologicalSort(Graph G)
{
//若G存在拓扑序列，返回true；否则返回false，说明有环
InitStack(S);
for(int i=0;i<G.vexnum;++i)
if(indegree[i]=0)
Push(S,i) //将所有入度为0的顶点进栈
int count=0; //记录当前已输出的顶点数
while(!IsEmpty(S)){
Pop(S, i);
print[count++]=i;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
//将所有i指向的顶点入度减1，若减去后为0则入栈
v=p->adjvex; //p是弧，adjvex是该弧指向的顶点的位置
if(!(--indegree[v]))
Push(S,v);
}
}
if(count<G.vexnum)
return false;
else
return true;
}
时间复杂度O(|V|+|E|)
用深度优先遍历也可以实现拓扑排序
若已知无环图，则可用拓扑排序来改进Dijkstra算法
以拓扑顺序来选取顶点，运行时间为O(|E|+|V|)
关键路径
用边表示活动的网络AOE网：在带权有向图中，以顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销。
1.只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
2.只有在进入某一顶点的各有向边所代表的活动都已结束，该顶点所代表的事件才能发生。
仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始。仅有一个出度为0的顶点，结束结点（汇点），表示整个工程的结束。
有些活动是可以并行进行的
从源点都汇点的路径可能有多条，所有路径上的活动都完成了整个工程才算结束，所以把路径长度最大的称为关键路径，其上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度。关键活动不能按时完成，则整个工程的完成时间都会受到影响。
事件Vk的最早发生时间Ve(k)
从开始顶点V到Vk的最长路径长度
Ve(V)=0
Ve(k)=Max{Ve(j)+Weight(Vj, Vk)}
从前往后计算
事件Vk的最迟发生时间Vl(k)
在不推迟整个工程完成的前提下，即保证它所指向的时间Vi在Ve(i)时刻能够发生时，该事件最迟必须发生的时间。
Vl(汇点)=Ve(汇点)
Vl(j)=Min{Vl(k)-Weight(Vj, vk)}
从后往前计算
活动Ai的最早开始时间E(i)
等于该活动的起点所表示的事件的最早发生时间
活动Ai的最迟开始时间L(i)
等于该活动的终点所表示的事件的最迟发生时间减去该活动所需要的时间
活动Ai可以拖延的时间D(i)
其最早开始时间与最迟开始时间的差值
若为0的话，就代表该活动必须要如期完成，否则会拖延完成整个工程的进度，则该活动是关键活动。
求关键路径过程.JPG
注意
网中的关键路径可能不止一条，这种情况时，只提高一条关键路径上的关键活动的速度并不能是整个工期变短。
存在一种称为“桥”的特殊关键活动，它位于所有关键路径上，只有加速它才能缩短整个工期。
//T为拓扑序列的顶点栈
bool TopologicalSort(ALGraph G, Stack &T)
{
InitStack(S);
for(int i=0;i<G.vexnum;++i)
if(indegree[i]=0)
Push(S,i)
int count=0;
ve[0......G.vexnum-1]=0; //初始化earliest
while(!IsEmpty(S)){
Pop(S, i);
Push(T, i); ++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v);
if(ve[j]+*(p->info)>ve[k]) //ve更新为更大的值
ve[k]=ve[j]+*(p->info);
}
}
if(count<G.vexnum)
return false;
else
return true;
}
Status CriticalPath(ALGraph G)
{
if(!TopologicalOrder(G, T) return Error;
vl[0......G.vexnum-1]=ve[G.venum-];
while(!StackEmpty(T)){
Pop(T, j);
for(p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
dut=*(p->info);
if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut; //vl更新为更小的值
}
}
for(j=0;j<G.vexnum;++j)
for(p=G.vertices[j].firstarc;p;p->nextarc){
k=p->adjvex; dut=*(p->info);
ee=ve[j]; el=vl[k]-dut;
//ee边p最早开始时间，el边p最晚开始时间
tag=(ee==el)?'*':' '; //*代表关键路径
printf(j,k,dut,ee,el,tag);
}
}
网友评论