算法:AOV网(Activity on Vextex Network)与拓扑排序

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

下面来看整体代码(改编自《大话数据结构》)

#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表示弧不存在。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

POJ3683 Priest John's Busiest Day(2-SAT)

Description John is the only priest in his town. September 1st is the John's bu...

3245
来自专栏云霄雨霁

算法设计策略----分治法

1510
来自专栏数据结构与算法

P1726 上白泽慧音

题目描述 在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够...

3206
来自专栏小樱的经验随笔

一步一步深入理解Dijkstra算法

先简单介绍一下最短路径: 最短路径是啥?就是一个带边值的图中从某一个顶点到另外一个顶点的最短路径。 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边...

2743
来自专栏数据结构与算法

P1049 装箱问题

题目描述 有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30,每个物品有一个体积(正整数)。 要求n个物品中,任取若干个装入箱...

2595
来自专栏java工会

12个入门级编程题目,工作三年会一半算你厉害!——答案明天见

1794
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

2696
来自专栏开发与安全

算法:图的广度优先遍历(Breadth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。 图...

19210
来自专栏数据结构与算法

P1726 上白泽慧音(0分)

题目描述 在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够...

2508
来自专栏数据结构与算法

BZOJ1007: [HNOI2008]水平可见直线(单调栈)

1081

扫码关注云+社区