精华内容
下载资源
问答
  • AOV网

    2019-09-28 03:46:42
    1、定义 用顶点表示活动,用有向边<Vi, Vj>表示活动间的优先关系。 Vi必须先于活动Vj进行。 这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices) ...这种构造AOV网络全部顶点的拓扑有序序列的运...

    1、定义

    用顶点表示活动,用有向边<Vi, Vj>表示活动间的优先关系。

    Vi必须先于活动Vj进行。

    这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)

     

    2、拓扑排序

    拓扑序列:即将各个顶点(代表各个活动)排列成一个线性有序的序列,使得所有弧尾结点排在弧头结点的前面。

     

    这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。

     

    如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则一定没有有向环。

     

    上图的拓扑排序为:

    C1,C8,C2,C3,C5,C9,C4,C7,C6

     

    拓扑排序方法:

    (1)输入AOV网络。令n为顶点个数;

    (2)在AOV网络中选一个没有直接前驱的顶点,并输出之;

    (3)从图中删去该顶点,同时删去所有它发出的有向边;

    (4)重复以上(2)(3)步,直到

             全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;

       或

             图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱,这是网络中必有环。

     

     

    如果图采用邻接表储存,则在邻接表中增设一个数组count[],记录各顶点入度。入度为0的顶点即无前驱顶点。

    在输入数据前,顶点表data[]和入度数组count[]全部初始化。

    在输入数据时,每输入一条边<j, k >,就需要建立一个边结点,并将它链入相应边链表中,统计入度信息:

    EdgeNode *p = new EdgeNode;
    p->adjvex = k;
    p->nextarc = G.VexList[j].firstarc;
    data[j].firstarc = p;
    count[k]++;
    

      

     

    在算法中,使用一个存放入度为0的顶点的链式栈,供选择和输出无前驱的顶点。

     

    算法描述:

    建立入度为0的顶点栈;

    当入度为0的顶点栈不为空时,重复执行

        从顶点栈中推出一个顶点,并输出之;

        从AOV网络中删去这个顶点和它发出的边,边的总顶点入度减一;

        如果边的终顶点入度减至0,则该顶点进入入度为0的顶点栈;

    如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。

     

    算法分析:

    如果AOV网络中有n个顶点,e条边,在拓扑排序的过程中,搜索入度为0的顶点,建立链式栈所需要的时间是O(n)。在正常的情况下,有向图有n个顶点,每个顶点进入一次栈,出一次栈,共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e).

    转载于:https://www.cnblogs.com/KennyRom/p/6120039.html

    展开全文
  • AOV网络

    千次阅读 2012-12-06 19:19:19
    人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工程,这些子工程被称为活动(Activity),在有向图中若以顶点表示活动,有向边表示活动之间的先后关系,这样的图简称为AOV网。...
     
    

    在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,一个工程常被分为多个小的子工程,这些子工程被称为活动(Activity),在有向图中若以顶点表示活动,有向边表示活动之间的先后关系,这样的图简称为AOV网。如下图是计算机专业课程之间的先后关系:

      图片注释:基础知识课程应先于其它所有课程, pascal 语言课程应先于 数据结构
      用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network),简称AOV网。
      在网中,若从顶点i到顶点j有一条有向路径,则i是j 的 前驱

      AOV网是一种有向无环图。

    算法如下:

    1:stack  S //用来存储入度为0的顶点

    2:count //用于输出的顶点计数器

    3:扫描所有的顶点,如果入度为0,则进栈

    4:取出栈顶顶点,输出,计数器加1,然后查找该顶点的所有邻接顶点,将这些顶点的入度减1,如果入度减至0,则进栈

    5:如果栈为空则停止循环,如果不为空继续执行第三步。

    6:循环退出后,检测计数器与顶点数目是否相等,如果计数器<顶点数目,则存在回路,不能拓扑排序成一个序列;如果计数器=定点数目,则AOV网络可行。


    下面代码:

    #include<iostream>
    #include<fstream>
    #include<stack>
    #include<vector>
    #include"F:\QQPCmgr\documents\visual studio 2010\Projects\Graph\Graph_matrix\GraphAdjMatrix.h"
    using namespace std;
    template<class T, class E>
    void TopologicalSort(GraphAdjMatrix<T,E> &targetG)
    {
    	int verticesNum = targetG.GetVerticesNum(); //获取图的顶点数目
    	int *in = new int[verticesNum]; //临时存储顶点的入度信息
    	targetG.GetInFormation(in); //调用图的接口,返回各个顶点的入度信息
    	
    	stack<int> stk; //栈 用来实现排序的中转
    	vector<int> veci; //容器 顺序存储每一个顶点
    	for(int i = 0; i < verticesNum; i++)
    	{
    		if(in[i] == 0)
    		{
    			stk.push(i); //扫描入度数组,把初始化状态入度为0的顶点进栈
    		}
    	}
    
    	int count = 0; //顶点计数器
    	int temp;
    	int adj;
    	int nullIdx = targetG.GetNullIdx();
    	while(stk.empty() == false)
    	{
    		temp = stk.top();
    		stk.pop();
    		veci.push_back(temp);
    		count++;
    
    		adj = targetG.GetVerticesPos(targetG.GetFirstNeighbor(temp)); //获取当前顶点的邻接点
    		while(adj != nullIdx)
    		{
    			in[adj]--;
    			if(in[adj] == 0)
    			{
    				stk.push(adj);
    			}
    
    			adj = targetG.GetVerticesPos(targetG.GetNextNeighbor(temp, adj));
    		}// end of 小while
    	}// end of 大while
    
    	if(count < verticesNum)
    	{
    		cout<<"count = "<<count<<endl;
    		cout<<"图中有回路,不能形成拓扑排序序列"<<endl;
    	}
    	else
    	{
    		cout<<"拓扑排序序列:"<<endl;
    		for(vector<int>::size_type idx = 0; idx < veci.size(); idx++)
    		{
    			cout<<"#"<<idx<<":"<<veci[idx]<<"  ";
    		}
    		cout<<endl;
    	}
    }

    展开全文
  • 活动网络——AOV网络

    2017-02-16 14:39:59
    AOV网络

    一般一个工程可以分成若干个子工程,这些子工程称为活动。实际上,可以用有向图来表示一个工程,用有向边<u,v>表示活动u必须先于活动v完成。这种有向图叫做顶点表示活动的网络,记作AOV网络(Activity On Vertices)。u成为v的直接前驱,v叫做u的直接后继,如果存在路径<u,u1,u2,u3.......v>,则称u是v的前驱,v是u的后继。任何活动不能以他自己为前驱或者后继,这种特性称为反自反性,AOV网络中不能出现有向回路。不含有向回路的有向图称为有向无环图,对于给定的AOV网络,必须先判断它是否是有向无环图。

    拓扑排序:判断有向无环图的方法是对AOV网络构造它的拓扑有序序列,即将各个顶点排列成一个线性有序的序列。

    实现方法:(1)从AOV网络中选取一个入度为0的顶点并输出

    (2)从AOV网络中删除该顶点及该顶点发出的所有边

    (3)重复步骤(1)(2),直到找不到入度为0的顶点

    按照上述方法进行拓扑排序,其结果有两种情形:(1)所有的顶点都被输出,也就是整个拓扑排序完成了 (2)仍有顶点没有被输出,但剩下的图中再也没有入度为0的顶点,这样拓扑排序就不能再继续进行下去了,说明此图是有向环图。

    例题:对输入的有向图进行拓扑排序,并输出一个拓扑排序序列。如果存在有向环,则给出提示信息。             

    输入描述:先输入顶点数n和边数m,然后输出m条边。

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    #define MAXN 10
    struct ArcNode
    {
        int to;
        ArcNode *next;
    };
    int n,m;
    ArcNode *list[MAXN];
    int count[MAXN];
    char output[100];
    void TopSort();
    int main()
    {
        int i,j;
        int u,v,w;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            if(n==0&&m==0) break;
            memset(list,0,sizeof(list));
            memset(count,0,sizeof(count));
            memset(output,0,sizeof(output));
            ArcNode *temp;
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&u,&v);
                u--;
                v--;
                count[v]++;
                temp=new ArcNode;
                temp->to=v;
                temp->next=NULL;
                if(list[u]==NULL)
                    list[u]=temp;
                else
                {
                    temp->next=list[u];
                    list[u]=temp;
                }
            }
            TopSort();
            for(i=0;i<n;i++)
            {
                temp=list[i];
                while(temp!=NULL)
                {
                    list[i]=temp->next;
                    delete temp;
                    temp=list[i];
                }
            }
        }
        return 0;
    }
    void TopSort()///拓扑排序
    {
        int i,j,top=-1;
        ArcNode *temp;
        bool bcycle=false;/// 是否存在有向环的标志
        int pos=0;///写入output数组的位置
        for(i=0;i<n;i++)///入度为0的点入栈
        {
            if(count[i]==0)
            {
                count[i]=top;
                top=i;
            }
        }
        for(i=0;i<n;i++)
        {
            if(top==-1)///栈为空,存在有向回路
            {
                bcycle=true;
                break;
            }
            else
            {
                j=top;///栈顶点j出栈
                top=count[top];
                pos+=sprintf(output+pos,"%d ",j+1);///返回值为这一次写入的字符串的长度
                temp=list[j];
                ///遍历顶点j的边链表,每条出边的终点入度减一
                while(temp!=NULL)
                {
                    int k=temp->to;
                    count[k]--;
                    if(count[k]==0)
                    {
                        count[k]=top;
                        top=k;
                    }
                    temp=temp->next;
                }
            }
        }
        if(bcycle)
            printf("Network has a cycle\n");
        else
        {
            int len=strlen(output);
            output[len-1]=0;///去掉最后的空格
            printf("%s\n",output);
        }
    }
    



    展开全文
  • AOV网络与AOE网络

    万次阅读 多人点赞 2018-06-05 20:43:07
      AOV网(Activity On Vertex NetWork)用顶点表示活动,边表示活动(顶点)发生的先后关系。   若网中所有活动均可以排出先后顺序(任两个活动之间均确定先后顺序),则称网是拓扑有序的。 1、算法步骤 在...

    一、AOV网络与拓扑排序

      AOV网(Activity On Vertex NetWork)用顶点表示活动,边表示活动(顶点)发生的先后关系。

      若网中所有活动均可以排出先后顺序(任两个活动之间均确定先后顺序),则称网是拓扑有序的。

    1、算法步骤

    • 在网络中选择一个入度为0的顶点输出;
    • 在图中删除该顶点及所有以该顶点为起点的边;
    • 重复上述过程,直至所有边均被输出。

    2、算法图解

    这里写图片描述

    3、算法demo:

    #include <bits/stdc++.h>
    using namespace std;
    
    const int  M  = 10001;
    int matrix[M][M];
    int indegree[M]; //book已排序的顶点个数
    
    int main(int argc, char const *argv[])
    {
        int i, j, a, b, k, book = 0, n, m;
        cin >> n >> m;
        for (i = 1; i <= m; ++i)
        {
            cin >> a >> b;
            matrix[a][b]=1;
            indegree[b]++;
        }
        for (i = 1; i <= n; ++i) 
        {
            for (j = 1; j <= n; ++j) 
            {
                if (indegree[j] == 0) 
                { 
                    cout << j << " ";
                    //遍历所有入度为0的顶点
                    indegree[j] = -1;
                    book++;
                    for (k=1; k <= n; k++)
                    {
                       if (matrix[j][k] == 1)
                        {
                            //遍历所有入度为1的顶点
                            matrix[j][k] = 0;
                            indegree[k]--;
                        }
                   }
                   break;
                }
            }
        }   
        system("pause");
        return 0;
    }

    二、AOE网络

      AOE网的定义:在带权有向图中若以顶点表示事件,有向边表示活动,边上的权值表示该活动持续的时间,这样的图简称为AOE网。
    这里写图片描述

      如上所示,共有11项活动(11条边),9个事件(9个顶点)。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点(源点)和只有一个出度为零的点(汇点)。
      关键路径:是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示,1 到2 到 5到7到9是关键路径(关键路径不止一条,请输出字典序最小的),权值的和为18。

    三、AOV网络与AOE网络的关系

      从定义上来看,很容易看出两种网的不同,AOV网的活动以顶点表示,而AOE网的活动以有向边来表示,AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图,其实它们总体网络结构是一样的,仅仅是活动所表示的方式不同,因此可以猜想从AOV网转换成AOE网应该是可行的。

      通常AOE网都是和关键路径联系在一起的,在AOE网中我们可以通过关键路径法来计算影响整个工期的关键路径,达到缩短工期的目的。在传统的AOV网中是没有表示活动时间的权值的,因此传统的AOV网无法估算工期,但是如果我们在AOV网中的活动结点上都标上时间属性,那么AOV网就可以完全转换为AOE网。

    展开全文
  • 一:AOV网(Activity On Vertex Network)【顶点——表示活动】 二:AOE网(Activity On Edge)【边——表示活动】 一:AOV网(Activity On Vertex Network)【顶点——表示活动】 是一个——有向无回路的图 ...
  • AOV网络和AOE网络

    千次阅读 2018-12-02 22:41:29
    AOV和AOE网络是什么 活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。活动网络可分为两种:AOV网络和AOE网络 AOV网络(Activity On Vertices):在有向图中,用顶点表示...
  • AOV网和AOE网

    2019-01-23 15:50:34
    1、AOV网 定义:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们成为AOV网(Activity On Vertex Network),AOV网中的弧表示活动之间的某种约束关系...
  • AOE网与AOV网

    2016-03-02 20:09:00
    AOV网(Activity On Vertex NetWork)用顶点表示活动,边表示活动(顶点)发生的先后关系。AOV网的边不设权值,若存在边<a,b>则表示活动a必须发生在活动b之前。 若网中所有活动均可以排出先...
  • 图论- AOV 与拓扑排序.rar
  • AOV网(Activity On Vertex Network) 拓扑排序(Topological Sort) 拓扑排序 – 思路 拓扑排序 – 实现 AOE网 (Activity On Edge Network) AOV网与AOE网的关系 AOV网(Activity On Vertex Network) 一项大...
  • AOV网的拓扑序列生成

    2010-12-09 12:46:20
    AOV网的拓扑序列生成 数据结构 设计程序完成如下功能:对给定的AOV网,产生所有的拓扑序列。提示:选择合适的数据结构表示AOV网
  • AOV网与拓扑排序

    2021-08-29 18:43:39
    AOV网 几乎所有的工程都可分为若干个称为活动的子工程,而这些子工程之间通常受到一些条件的制约,如某些子工程必须要在其它子工程完成之后才能进行。用图的顶点表示子工程(活动),用弧表示活动之间的优先关系的有...
  • 图5——AOV网和AOE网

    2019-12-02 22:46:15
    AOV网: 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网。 特点: 1.AOV网中的弧表示活动之间存在的某种制约关系。 2.AOV网中不能出现回路 ...
  • AOV网与工作流网的区别与联系
  • 数据结构:图:AOV网和AOE网

    千次阅读 2019-06-12 16:26:17
    AOV网(顶点表示活动的网):以有向图中的顶点来表示活动,以有向边来表示活动之间的先后次序关系。 AOV网的拓扑序列:AOV网的拓扑序列就是将AOV网中的所有顶点排成一个线性序列;拓扑序列实际上就是要由某个集合上...
  • 【算法】 AOV网与AOE网

    2019-09-10 21:02:16
    AOV网 我们把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待,所有的工程都可以分为若干个“活动”的子工程。有很多场景对顺序有严格的要求,比如说建造一栋大楼必须先找好施工人员,购买各种...
  • 图的应用(AOV网、AOE网、图连通性): AOV网: 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网AOV网特点: 1.AOV网中的弧表示活动之间...
  • 【笔记】AOV网与拓扑排序

    千次阅读 2017-12-01 13:07:58
    无环路有向图 AOV网 拓扑排序 AOV网的拓扑排序算法实现
  • 1.AOV网:顶点活动网,是指用顶点表示活动,而用边集表示活动优先关系的有向无环图。 2.AOE网:边活动网,是指用带权的边集表示活动,而用顶点表示事件的有向无环图。 AOV网和AOE网都不能存在环,否则会出现逻辑错误...
  • 针对印刷工作流程的控制问题,首先在研究JDF(job definition format)标准的基础上,基于AOV(activity on vertices)网提出了JDF-AOV网,以描述JDF印刷工作流程中各过程节点在执行时的相互依赖关系;然后定义了...
  • AOV网和AOE网对比

    2013-06-25 04:27:00
    AOV网和AOE网对比 转载于:https://www.cnblogs.com/LoveFishC/p/3846907.html

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,451
精华内容 1,780
关键字:

aov网