AOV网与拓扑排序#

AOV网#

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称 AOV网(activity on vertex network)。

AOV网中的弧表示了活动之间存在的某种制约关系。在AOV网中不能出现回路，否则意味着某活动的开始要以自己的完成为先决条件，显然，这是荒谬的。因此判断AOV网所代表的工程是否能顺利进行，即判断它是否存在回路。而测试AOV是否存在回路的方法，就是对AOV网进行拓扑排序。

拓扑排序#

设 $G=(V,E)$ 是一个有向图， $V$ 中的顶点序列 $v_0,v_1,...,v_{n-1}$ 称为一个拓扑序列，当且仅当满足下列条件：若顶点从 $v_i$ 到 $v_j$ 有一条路径，则在顶点序列中 $v_i$ 必须在 $v_j$ 之前。对一个有向图构造拓扑序列的过程称为拓扑排序。

拓扑排序算法#

算法思想#

找到没有入度的结点，输出并将相关边删除
重复1，直到没有入度为 0 的顶点
若全部顶点都被输出，则说明没有环路，否则说明有环路

算法设计#

为了防止每次遍历所有顶点，可以用栈来存储，每次只找出栈的顶点的边指向的顶点。
遍历一次邻接矩阵，计算所有顶点的入度
遍历一次顶点，把入度为 0 的顶点入栈
获得栈顶顶点，输出并减少相关顶点的入度，当入度减少为 0 时，将该顶点入栈
循环 4 直到栈空

算法实现#

代码实现：

1
// 拓扑排序
2
/*
3
g：图的邻接矩阵
4
n：顶点个数
5

6
return：拓扑序列
7
*/
8
int* graph_topSort(int** g, int n)
9
{
10
    // 存储每个结点的入度
11
    int* g_in = utils_createArr(n, 0);
12

13
    int count_in;
14
    for(int i = 0; i < n; i ++)
15
    {
16
        count_in = 0;
17
        for(int j = 0; j < n; j ++)
18
        {
19
            // 每一列边的个数表示顶点的入度
20
            if(g[j][i] != -1) count_in++;
21
        }
22
        g_in[i] = count_in;
23
    }
24

25
    // 创建栈
26
    SNode* ts_stack = createStack();
27

28
    int i_tmp;
29
    // 记录拓扑序列顺序的数组
30
    int* ts_seq = utils_createArr(n,-1);
31
    // 记录拓扑序列数组中元素的个数
32
    int ts_seq_i = 0;
33

34
    // 将入度为0的顶点入栈
35
    for(int i = 0; i < n; i ++)
36
    {
37
        if(g_in[i] == 0)
38
        {
39
            // 将初始入度为 0 的顶点入栈
40
            stack_push(ts_stack, createSNode(i));
41
        }
42
    }
43

44
    // 当栈为空时，退出循环
45
    while(stack_getLen(ts_stack))
46
    {
47
        i_tmp = stack_pop(ts_stack)->value;
48

49
        for(int i = 0; i < n; i ++)
50
        {
51
            // i_tmp 删除所有边相关的入度
52
            if(g[i_tmp][i] != -1)
53
            {
54
                g_in[i]--;
55
                // 当有个顶点的入度因为去掉当前边而变为0时，将其入栈
56
                if(g_in[i] == 0)
57
                    stack_push(ts_stack, createSNode(i));
58
            }
59
        }
60

61
        // 记录拓扑序列
62
        ts_seq[ts_seq_i++] = i_tmp;
63
    }
64

65
    // 当拓扑序列没有排满时，说明有回路
66
    if(ts_seq_i < n)
67
    {
68
        printf("有回路\n");
69
        // 返回空
70
        return NULL;
71
    }
72
    return ts_seq;
73
}

测试样例：

在这里插入图片描述

测试代码：

1
int main()
2
{
3
    // 边数组，i%3=0 表示起点；i%3=1 表示终点；i%3=2 表示权值
4
    int arr[27] = {1,0,1,1,3,1,2,0,1,2,3,1,3,0,1,4,2,1,4,3,1,4,5,1,3,5,1,0,1,1};
5
    int n = 6; // 结点个数
6
    char vs[6] = {'A','B','C','D','E','F'};
7
    int** g = graph_createArrInValue(n, -1);
8
    // 创建相关邻接矩阵
9
    graph_createAdjacencyMatrixByArrWithWeight(g,arr, 27, 1);
10

11
    printf("原图邻接矩阵：\n");
12
    graph_print(g, n, "%3d ");
13
    printf("\n");
14
    int* ts = graph_topSort(g, n);
15

16
    printf("拓扑序列：");
17
    for(int i = 0; i < n; i ++)
18
        printf("%c ", vs[ts[i]]);
19

20
    return 0;
21
}

运算结果：

在这里插入图片描述

原文链接：CSDN