AOV网与拓扑排序

2023-01-04 23:15:57

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Activity on Vextex Network)。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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#include<iostream>
using 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;
    G->arc[0][11] = 1;
    G->arc[1][2] = 1;
    G->arc[1][4] = 1;
    G->arc[1][8] = 1;
    G->arc[2][5] = 1;
    G->arc[2][6] = 1;
    G->arc[2][9] = 1;
    G->arc[3][2] = 1;
    G->arc[3][13] = 1;
    G->arc[4][7] = 1;
    G->arc[5][8] = 1;
    G->arc[5][12] = 1;
    G->arc[6][5] = 1;
    G->arc[8][7] = 1;
    G->arc[9][10] = 1;
    G->arc[9][11] = 1;
    G->arc[10][13] = 1;
    G->arc[12][9] = 1;

}

/* 利用邻接矩阵构建邻接表 */
void CreateALGraph(MGraph G, GraphAdjList *GL)
{
int i, j;
EdgeNode *e;

*GL = (GraphAdjList)malloc(sizeof(graphAdjList));

(*GL)->numVertexes = G.numVertexes;
    (*GL)->numEdges = G.numEdges;
    for(i = 0; i < G.numVertexes; i++) /* 读入顶点信息，建立顶点表 */
    {
        (*GL)->adjList[i].in = 0;
        (*GL)->adjList[i].data = G.vexs[i];
        (*GL)->adjList[i].firstedge = NULL;     /* 将边表置为空表 */
    }

for(i = 0; i < G.numVertexes; i++) /* 建立边表 */
    {
        for(j = 0; j < G.numVertexes; j++)
        {
            if (G.arc[i][j] == 1)
            {
                e = (EdgeNode *)malloc(sizeof(EdgeNode));
                e->adjvex = j;                  /* 邻接序号为j  */
                e->next = (*GL)->adjList[i].firstedge;  /* 将当前顶点上的指向的结点指针赋值给e */
                (*GL)->adjList[i].firstedge = e;        /* 将当前顶点的指针指向e  */
                (*GL)->adjList[j].in++; /* 注意这里是j */

}
}
}

}
/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */
bool TopologicalSort(GraphAdjList GL)
{
    EdgeNode *pe;
    int i, k, gettop;
    int top = 0;/* 用于栈指针下标  */
    int count = 0;/* 用于统计输出顶点的个数  */
    /* 建栈将入度为0的顶点入栈  */
    int *stack = (int *)malloc(sizeof(GL->numVertexes * sizeof(int)));

for (i = 0; i < GL->numVertexes; i++)
if (0 == GL->adjList[i].in)
stack[++top] = i;/* 将入度为0的顶点入栈 */

while (top != 0)
    {
        gettop = stack[top--];
        cout << GL->adjList[gettop].data << " -> ";
        count++;  /* 输出i号顶点，并计数 */
        for (pe = GL->adjList[gettop].firstedge; pe; pe = pe->next)
        {
            k = pe->adjvex;
            /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */
            if (!--GL->adjList[k].in)
                stack[++top] = k;
        }
    }
    cout << endl;
    if (count < GL->numVertexes)
        return false;
    else
        return true;
}

int main(void)
{
    MGraph MG;
    GraphAdjList GL;
    CreateMGraph(&MG);
    CreateALGraph(MG, &GL);
    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表示弧不存在。

当然程序输出的结果并不是唯一的一种拓扑排序方案。

码农公寓

相关文章