AOV网(Activity on Vertex Network)与拓扑排序

夯实基础

AOV网(Activity on Vertex Network)

用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV网。
在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工程,这些子工程被称为活动(Activity),在有向图中若以顶点表示活动,有向边表示活动之间的先后关系,这样的图简称为AOV网。

  • AOV网是一种有向无回路的图。
  • 在网中,若从顶点i到顶点j有一条有向路径,则ij的前驱。
  • AOV网中的弧表示了活动之间先后次序存在的制约关系。必须先完成前一个,才能完成下一个。必须先小学毕业,才能初中毕业。

拓扑排序

AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)
AOV网构造拓扑序列的实际的意义:如果按照拓扑序列中的顶点次序,在开始每一项活动时,能够保证它的所有前驱活动都已完成。

AOV网进行拓扑排序的步骤如下

  • AOV网中选一个没有前驱的顶点(该顶点的入度为0),并输出它。
  • AOV网中山区该顶点以及以它为弧尾的所有有向边。
  • 重复上述两个步骤,知道剩余的网中不再存在没有前驱的节点。

快速通道 图的邻接表存储

1
2
3
4
5
6
7
8
9
10
11
12
邻接表结构的类型
typedef struct edge { //边
int adjvex; // 该边的终止顶点在顶点结点中的位置,数组的key
int weight;
struct edge *next;
} Elink;

typedef struct ver {
int indegree; //顶点的入度
vertype vertex;
Elink * link;
}TOPOVlink;

拓扑排序的算法思想

  1. 将所有没有前驱的顶点(indegree=0),压入链接栈。
  2. 当堆栈不空时,从栈中退出栈顶元素并输出,并把该顶点引出的所有有向边删除,同时分别把他的各个邻接顶点的入度减一(indegree-1)
  3. 将新的入度为0的顶点亚茹堆栈。
  4. 重复2和3步骤,知道输出全部顶点或图中剩余顶点里不在有入度为0的顶点。
xpisme wechat
微信号