C语言AOV网，拓扑排序完整算法实现

野性酷女 2022-04-25 03:24 273阅读 0赞

**目录**

1.AOV网（Activity On Vertex Network）

2.拓扑排序（Topological Sort）

2.1拓扑排序概念

2.2拓扑排序算法

2.3拓扑排序举例

3.源代码示例

--------------------

## 1.AOV网（Activity On Vertex Network） ##

在分析和实施一些工程时，会根据需要将工程分成若干个小工程，这些小工程称为活动。当这些小工程完成时，整个工程也就完成了。这些活动之间存在两种关系：

（1）先后关系：必须在某个（某些）活动完成后，才能进行下个活动

（2）无关系：两个或以上的活动可以并行进行

因此可以用一个有向图来表示各个活动之间的关系。用顶点代表活动，有向边表示活动间的先后关系。

我们把这种用顶点表示活动，用弧表示活动之间优先关系的有向图称为AOV网

## 2.拓扑排序（Topological Sort） ##

### 2.1拓扑排序概念 ###

在AOV网中，若不存在回路，则所有活动都可以排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列称为有向图的一个拓扑序列（Topoligical Order）。构造一个有向图的拓扑序列的过程称为拓扑排序。

### 2.2拓扑排序算法 ###

（1）在有向图中选择一个入度为 0 的顶点，输出该节点

（2）从图中删除该顶点和所有以它为始点（弧尾）的弧

（3）重复步骤（1）（2）直到找不到入度为 0 的顶点，拓扑排序完成

若最后图中仍有节点存在，却没有入度为 0 的顶点，说明AOV网中有环存在。

### 2.3拓扑排序举例 ###

图 (a) 是一有向图，其邻接链表结构如图 (b) 所示，在表头向量中增加了一个域 id，用来存放图中各顶点的入度；实现拓扑排序可设一个栈，用来存放入度为 0 的顶点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

下面是描述拓扑排序的全过程：

1.  将入度为 0 的顶点压栈，如图 (b) 所示；
2.  取栈顶元素 C4，输出 C4，删除 C4 和所有以它为始点的弧 e3、e4、C3 的入度减 1，C5 的入度减 1，C5 的入度变为 0，C5 入栈，如图 (c) 所示；
3.  取栈顶元素 C5，输出 C5，删除 C5 和所有以它为始点的弧 e7，C6 入度减 1，如图 (d) 所示；
4.  取栈顶元素 C1，输出 C1，删除 C1 和所有以它为始点的弧 e1，e2，C2的入度减 1，C2 的入度变为 0，C2 入栈，C3 的入度减1，C3 的入度变为 0，C3 入栈，如图(e)所示；
5.  取栈顶元素 C3，输出 C3，删除 C3 和所有以它为始点的弧 e6，C6 的入度减 1，如图 (f) 所示；
6.  取栈顶元素 C2，输出 C2，删除 C2 和所有以它为始点的弧 e5，C6 的入度减 1，C6 的入度为 0，C6 入栈，如图（g）所示；
7.  取栈顶元素 C6，输出 C62，删除 C6，没有以它为始点的弧，栈空，如图（h）所示；
8.  栈空，算法结束，拓扑序列为：C4，C5，C1，C3，C2，C6。

## 3.源代码示例 ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VERTEX_NUM 100 // 有向图中最大节点数
    typedef char VexType;      // 定义节点名为char型
    typedef struct node        // 弧表节点
    {
        VexType adjvex;    // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node *next; // 指向顶点的下一个邻接点
    } EdgeNode;
    
    typedef struct vnode // 顶点结构
    {
        int ID;              // 顶点入度( in-degree )
        VexType vex;         // 存储顶点名
        EdgeNode *firstedge; // 弧表头指针，指向顶点第一个邻接点
    } VexNode, AdjList[MAX_VERTEX_NUM];
    
    typedef struct {
        AdjList adjlist; // 描述有向图结构的邻接表
        int vexnum;      // 节点的数目
        int edgenum;     // 弧的数目
    } ALGraph;           // adjacency list：邻接表
    
    void CreateDG(ALGraph *DG);       // 邻接表法创建有向图
    void TraverseDG(ALGraph DG);      // 遍历有向图DG
    void TopologicalSort(ALGraph DG); // 对有向图DG拓扑排序
    void LocateVex(ALGraph DG, VexType vex, int *index);
    // 若有向图DG中存在节点vex，则将该下标赋给index
    
    int main(void)
    {
        ALGraph g;
    
        CreateDG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        TraverseDG(g);
        printf("------------------------------\n");
        TopologicalSort(g);
    
        return 0;
    }
    void CreateDG(ALGraph *DG)
    {
        VexType ch;
        int i = 0;
        int start, end; // start:弧尾下标；end:弧头下标
        EdgeNode *temp;
    
        printf("请输入有向图的顶点数、弧数：");
        scanf("%d%d", &(DG->vexnum), &(DG->edgenum));
    
        printf("请输入有向图的顶点：");
        getchar();
        while ((ch = getchar()) != '\n') // 建立顶点表
        {
            DG->adjlist[i].vex = ch;
            DG->adjlist[i].firstedge = NULL;
            DG->adjlist[i].ID = 0;
            i++;
        }
    
        printf("顶点 | 下标\n");
        for (i = 0; i < DG->vexnum; i++) // 显示有向图中顶点及其对应下标
            printf("%3c%6d\n", DG->adjlist[i].vex, i);
    
        printf("请依次输入每条弧的弧尾下标、弧头下标：\n");
        for (i = 0; i < DG->edgenum; i++) // 头插法建立顶点的邻接弧表
        {
            scanf("\n%d%d", &start, &end);
            while (start < 0 || start > (DG->vexnum - 1) || end < 0 ||
                   end > (DG->vexnum - 1)) {
                printf("下标越界，重新输入：");
                scanf("\n%d%d", &start, &end);
            }
    
            temp = (EdgeNode *)malloc(sizeof(EdgeNode));
            temp->adjvex = DG->adjlist[end].vex;
            temp->next = DG->adjlist[start].firstedge;
            DG->adjlist[start].firstedge = temp;
            DG->adjlist[end].ID++;
        }
    }
    void TraverseDG(ALGraph DG)
    {
        int i;
        EdgeNode *temp;
    
        if (DG.vexnum == 0) {
            printf("有向图为空\n");
            return;
        }
    
        for (i = 0; i < DG.vexnum; i++) // 遍历有向图
        {
            printf("顶点 %c ( ID = %d ) ：", DG.adjlist[i].vex, DG.adjlist[i].ID);
            temp = DG.adjlist[i].firstedge;
            while (temp) // 输出有向图的信息
            {
                printf("[ %c ] -> ", temp->adjvex);
                temp = temp->next;
            }
            printf("NULL\n");
        }
    }
    void TopologicalSort(ALGraph DG)
    {
        int i, j, k, m = 0, top; // top：栈顶入度为 0 的顶点下标
        EdgeNode *temp;
    
        top = -1;
        for (i = 0; i < DG.vexnum; i++) // 让初始情况下入度为0的顶点入栈
            if (DG.adjlist[i].ID == 0) {
                DG.adjlist[i].ID =
                    top; // 用入度为0的新顶点的ID存储旧入度为0的顶点下标
                top = i; // top始终指向栈顶入度为0的顶点下标
            }
    
        printf("有向图的拓扑序列为：");
        while (top != -1) {
            j = top;                  // 栈顶顶点下标赋给j
            top = DG.adjlist[top].ID; // 输出栈顶节点后，top下移，指向新的栈顶节点
            printf("%c, ", DG.adjlist[j].vex); // 输出栈顶节点
            m++;
            temp = DG.adjlist[j].firstedge;
    
            while (temp != NULL) // 遍历顶点所有邻接点
            {
                LocateVex(DG, temp->adjvex, &k);
                DG.adjlist[k].ID--;
                if (DG.adjlist[k].ID == 0) {
                    DG.adjlist[k].ID =
                        top; // 用入度为0的新顶点的ID存储旧入度为0的顶点下标
                    top = k; // top始终指向栈顶入度为0的顶点下标
                }
                temp = temp->next;
            }
        }
    
        if (m < DG.vexnum) // 若输出顶点数小于总顶点数，网中有环
            printf("网中有环！\n");
    }
    void LocateVex(ALGraph DG, VexType vex, int *index)
    {
        int i;
    
        for (i = 0; i < DG.vexnum; i++) {
            if (DG.adjlist[i].vex == vex) {
                *index = i;
                return;
            }
        }
        printf("该节点不存在！\n");
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220210/0f0d2a0211ec44c1957ad3f468c35fc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220210/632bf78a8ac344ee8c368fc6136ca925.png