算法: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 条评论
登录 后参与评论

相关文章

来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

822
来自专栏恰同学骚年

数据结构基础温故-1.线性表(中)

在上一篇中,我们学习了线性表最基础的表现形式-顺序表,但是其存在一定缺点:必须占用一整块事先分配好的存储空间,在插入和删除操作上需要移动大量元素(即操作不方便)...

712
来自专栏趣学算法

数据结构 第15讲 一场说走就走的旅行——最短路径

本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

891
来自专栏程序生活

图的广度优先搜索和深度优先搜索(邻接链表表示)邻接链表广度优先搜索深度优先搜索运行结果

邻接链表 邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它...

3824
来自专栏计算机视觉与深度学习基础

Leetcode 239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from t...

1835
来自专栏温安适的blog

最小生产树Prim和Kruskal

40912
来自专栏杨熹的专栏

Pandas常用命令-1

初期的时候,可能会先从实例入手,而不是先把所有先备命令学一遍,但下面这几个命令还是经常用的,如果被很长的tutorial吓跑,可以先敲一遍这些命令。 impor...

3416
来自专栏开发与安全

算法:最短路径之迪杰斯特拉(Dijkstra)算法

对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Di...

1725
来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

783
来自专栏CodingBlock

Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析

前言:排序在算法中的地位自然不必多说,在许多工作中都用到了排序,就像学生成绩统计名次、商城商品销量排名、新闻的搜索热度排名等等。也正因为排序的应用范围如此之广...

2099

扫码关注云+社区