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

相关文章

来自专栏小樱的经验随笔

Codeforces 626G Raffles(贪心+线段树)

G. Raffles time limit per test:5 seconds memory limit per test:256 megabytes inp...

2505
来自专栏desperate633

LeetCode 160. Intersection of Two Linked Lists题目分析

请写一个程序,找到两个单链表最开始的交叉节点。 ** 注意事项 ** 如果两个链表没有交叉,返回null。 在返回结果后,两个链表仍须保持原有的结构。 ...

862
来自专栏赵俊的Java专栏

翻转链表

1233
来自专栏书山有路勤为径

链表求环

LeetCode 141. Linked List Cycle 142.Linked List Cycle II

812
来自专栏mathor

LeetCode86. 分隔链表

 这道题类似荷兰国旗,说一下做法,最简单的方法就是直接将所有的值保存到数组中,然后对数组进行划分,完了以后再重新插回链表中。但是这道题有一个附加要求,要保留...

835
来自专栏武培轩的专栏

剑指Offer-链表中环的入口结点

package LinkedList; import java.util.HashSet; /** * 链表中环的入口结点 * 一个链表中包含环,请找出...

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

Leetcode 142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cyc...

1969
来自专栏菩提树下的杨过

委托示例(利用委托对不同类型的对象数组排序)

using System; using System.Collections.Generic; using System.Text; namespac...

2149
来自专栏技术换美食换不换

matplotlib

722
来自专栏calmound

Linked List Cycle

问题:判断链表是否有环。 分析:利用快慢指针slow,fast          slow指针每次走一步,fast指针每次走两步,倘若存在环,则slow和fas...

2814

扫码关注云+社区