AOV网与拓扑排序

在⼀个表⽰⼯程的有向图中，⽤顶点表⽰活动，⽤弧表⽰活动之间的优先关系，这样的有向图为顶点表⽰活动的⽹，我们称之为AOV⽹（Activity on VextexNetwork)。AOV⽹中的弧表⽰活动之间存在的某种制约关系，AOV⽹中不能存在回路，让某个活动的开始要以⾃⼰完成作为先决条件，显然是不可以的。设G= { V, E }是⼀个具有n个顶点的有向图，V中的顶点序列v1, v2, ...，vn，满⾜若从顶点vi到vj有⼀条路径，则在顶点序列中顶点vi必在vj之前，则我们称这样的顶点序列为⼀个拓扑排序。

所谓拓扑排序，其实就是对⼀个有向图构造拓扑序列的过程。构造时会有两个结果，如果此⽹的全部顶点都被输出，则说明它是不存在（回路）的AOV⽹；如果输出顶点少了，哪怕是少了⼀个，也说明这个⽹存在环路，不是AOV⽹。

对AOV⽹进⾏拓扑排序的基本思路是：从AOV⽹中选择⼀个⼊度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV⽹中不存在⼊度为0的顶点为⽌。

由于在拓扑排序的过程中，需要删除顶点，显然⽤的结构会更加⽅便，考虑到算法中始终要查找⼊度为0的顶点，我们可以在原来顶点表结点结构中，增加⼀个⼊度域in, 即⼊度的数字，上⾯所提到的删除以某个顶点为尾的弧的操作也是通过将某顶点的邻接点的in减去1，表⽰删除了中间连接的弧。对于图7-8-2的第⼀幅图AOV⽹，可以得到如第⼆幅图的邻接表数据结构。

另外，在算法中，还需要辅助的数据结构--栈，⽤来存储处理过程中⼊度为0的点，⽬的是为了避免每次查找时都要去遍历顶点表找有没有⼊度为0的顶点。下⾯来看整体代码（改编⾃《⼤话数据结构》）

C++ Code

1234567101112131415161718192021222324252627282930313233343536373839404142434445474849505152535455565758596061

#includeusing namespace std;#define MAXEDGE 20#define MAXVEX 14#define INFINITY 65535/* 邻接矩阵结构 */typedef struct{

int vexs[MAXVEX];

int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges;} MGraph;

/* 邻接表结构****************** */

typedef struct EdgeNode /* 边表结点 */{

int adjvex; /* 邻接点域，存储该顶点对应的下标 */

int weight; /* ⽤于存储权值，对于⾮⽹图可以不需要 */ struct EdgeNode *next; /* 链域，指向下⼀个邻接点 */} EdgeNode;

typedef struct VertexNode /* 顶点表结点 */{

int in; /* 顶点⼊度 */

int data; /* 顶点域，存储顶点信息 */ EdgeNode *firstedge;/* 边表头指针 */} VertexNode, AdjList[MAXVEX];

typedef struct{

AdjList adjList;

int numVertexes, numEdges; /* 图中当前顶点数和边数 */} graphAdjList, *GraphAdjList;/* **************************** */

void CreateMGraph(MGraph *G)/* 构建图 */{

int i, j;

/* printf(\"请输⼊边数和顶点数:\"); */ G->numEdges = MAXEDGE; G->numVertexes = MAXVEX;

for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ {

G->vexs[i] = i; }

for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ {

for ( j = 0; j < G->numVertexes; j++) {

G->arc[i][j] = 0; } }

G->arc[0][4] = 1; G->arc[0][5] = 1;

61 G->arc[0][11] = 1;62 G->arc[1][2] = 1;63 G->arc[1][4] = 1; G->arc[1][8] = 1;65 G->arc[2][5] = 1;66 G->arc[2][6] = 1;67 G->arc[2][9] = 1;68 G->arc[3][2] = 1;69 G->arc[3][13] = 1;70 G->arc[4][7] = 1;71 G->arc[5][8] = 1;72 G->arc[5][12] = 1;73 G->arc[6][5] = 1;74 G->arc[8][7] = 1;75 G->arc[9][10] = 1;76 G->arc[9][11] = 1;77 G->arc[10][13] = 1;78 G->arc[12][9] = 1;7980}81

82 /* 利⽤邻接矩阵构建邻接表 */83void CreateALGraph(MGraph G, GraphAdjList *GL)84{85 int i, j;86 EdgeNode *e;8788 *GL = (GraphAdjList)malloc(sizeof(graphAdjList));90 (*GL)->numVertexes = G.numVertexes;91 (*GL)->numEdges = G.numEdges;92 for(i = 0; i < G.numVertexes; i++) /* 读⼊顶点信息，建⽴顶点表 */93 {94 (*GL)->adjList[i].in = 0;95 (*GL)->adjList[i].data = G.vexs[i];96 (*GL)->adjList[i].firstedge = NULL; /* 将边表置为空表 */97 }99 for(i = 0; i < G.numVertexes; i++) /* 建⽴边表 */100 {101 for(j = 0; j < G.numVertexes; j++)102 {103 if (G.arc[i][j] == 1)104 {105 e = (EdgeNode *)malloc(sizeof(EdgeNode));106 e->adjvex = j; /* 邻接序号为j */107 e->next = (*GL)->adjList[i].firstedge; /* 将当前顶点上的指向的结点指针赋值给e */108 (*GL)->adjList[i].firstedge = e; /* 将当前顶点的指针指向e */109 (*GL)->adjList[j].in++; /* 注意这⾥是j */110111 }112 }113 }114115}116/* 拓扑排序，若GL⽆回路，则输出拓扑排序序列并返回1，若有回路返回0。 */117bool TopologicalSort(GraphAdjList GL)118{119 EdgeNode *pe;120 int i, k, gettop;121 int top = 0;/* ⽤于栈指针下标 */122 int count = 0;/* ⽤于统计输出顶点的个数 */123 /* 建栈将⼊度为0的顶点⼊栈 */124 int *stack = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));125126 for (i = 0; i < GL->numVertexes; i++)127 if (0 == GL->adjList[i].in)128 stack[++top] = i;/* 将⼊度为0的顶点⼊栈 */129130 while (top != 0)131 {132 gettop = stack[top--];133 cout << GL->adjList[gettop].data << \" -> \";134 count++; /* 输出i号顶点，并计数 */135 for (pe = GL->adjList[gettop].firstedge; pe; pe = pe->next)136 {137 k = pe->adjvex;138 /* 将i号顶点的邻接点的⼊度减1，如果减1后为0，则⼊栈 */139 if (!--GL->adjList[k].in)140 stack[++top] = k;141 }142 }143 cout << endl;144 if (count < GL->numVertexes)145 return false;146 else147 return true;148}149150int main(void)151{152 MGraph MG;153 GraphAdjList GL;154 CreateMGraph(&MG);155 CreateALGraph(MG, &GL);156

156157158159160161162163

if (TopologicalSort(GL))

cout << \"It's a AOV network\" << endl; else

cout << \"It's not a AOV network\" << endl; return 0;}

输出为：

算法的代码相⽐较最⼩⽣成树和最短路径是⽐较好理解的，注释也⽐较清楚，这⾥就不费⼝⾆了，如下图7-8-4是将结点v3被删除的模拟图，其他依次被删除的结点情形类似，可类推。需要注意的是上⾯有个通过邻接矩阵（事先确定）来⽣成邻接表的函数CreateALGraph，因为是有向图，所以针对⼀条边只插⼊⼀次EdgeNode, 且初始化in时注意是⼊度，即 (*GL)->adjList[j].in++; /* 注意这⾥是j */ 另外创建邻接矩阵的函数CreateMGraph中因为是有向图，故矩阵并不是对称的，需要注意。另外也不是⽹图，故只⽤1表⽰弧存在，0表⽰弧不存在。当然程序输出的结果并不是唯⼀的⼀种拓扑排序⽅案。