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

    2019-08-24 19:18:00
    顶点活动(Activity On Vertex,AOV)是指用顶点表示活动,而用边表示活动间优先关系的有向图。图中不能出现有向环,否则会让优先关系出现逻辑错误。 边活动(Activity On Edge,AOE)是指用带权的边集表示活动。而...

    顶点活动(Activity On Vertex,AOV)网是指用顶点表示活动,而用边表示活动间优先关系的有向图。图中不能出现有向环,否则会让优先关系出现逻辑错误。

    边活动(Activity On Edge,AOE)网是指用带权的边集表示活动。而用顶点表示事件的有向图。其中边权表示完成活动需要的时间。

    一般来说,AOE网用来表示一个工程的进行过程,而工程常常分为若干个子工程(即活动),显然,AOE网中不能有环,否则会出现和AOV网中一样的逻辑问题(因此可以认为AOV网和AOE网都是有向无环图)。考虑到对工程来说总会有一个起始时刻和结束时刻,因此AOV网一般只有一个源点(即入度为0的点)和一个汇点(即出度为0的点)。不过虽然这么说,实际上即便有多个源点和多个汇点,仍然可以转化为一个源点和一个汇点的情况。

    也就是添加一个“超级源点”和“超级汇点”的方法,即从超级源点出发,连接所有入度为0的点;从所有出度为0的点中,连接超级汇点;添加的有向边的边权为0.

    需要指出,如果给定AOV网中各顶点活动所需要的时间,那么就可以把AOV网转化为AOE网。比较简单的方法是,将AOV网中的每个顶点都拆成两个顶点,分别表示活动的起点和终点,而两个顶点之间用有向边来连接,该有向边表示原顶点的活动,边权给定;原AOV网中的边全部视为空活动,边权为0;

    既然AOE网是基于工程提出的概念,那么一定有其需要解决的问题,AOE网需要着重解决两个问题:

    1)工程起始到终止至少需要多少时间

    2)哪条(些)路径上的活动是影响整个工程进度的关键

    AOE网中的最长路径被称为关键路径(强调:关键路径就是AOE网中的最长路径),而把路径上的活动称为关键活动,显然关键活动会影响整个工程的进度。

     

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

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

    AOV和AOE网络是什么

    活动网络可以用来描述生产计划、施工过程、生产流程、程序流程等工程中各子工程的安排问题。活动网络可分为两种:AOV网络和AOE网络

    AOV网络(Activity On Vertices):在有向图中,用顶点表示活动,用有向边u->v来表示活动u必须先于活动v进行

    AOE网络(Activity on edge network):若在带权的有向图中,以顶点表示阶段,以有向边u->v表示活动活动u必须先于活动v进行,边上的权值表示活动的开销(如该活动持续的时间)

     针对AOV网络的拓扑排序算法

    为AOV网络进行管理:决定每个结点的先后顺序(不一定是唯一的),也就决定了活动的先后顺序

    拓扑排序(Topological Sort)见:算法导论第22章:基本的图算法

    针对AOE网络的关键路径算法 

    关键路径(Critical Path):从源点到汇点具有最大长度的路径。这条路径决定了整个项目的最早完成时间,要想优化整个项目的时间,则必须在关键路径上下手。

    最早完成时间:项目到达某个阶段至少需要的时间,即源点到相应顶点的最长路径。

    最迟完成时间:项目最迟完成的时间,超过此时间表示项目产生了停滞。

    **算法思想:拓扑序DP**

    算法描述

    从源点开始,更新其所有邻接结点的最早完成时间,直到汇点(项目的终止点)

    按拓扑逆序DP,获得所有结点的最迟完成时间

    若最早完成时间 == 最迟完成时间,则证明其为关键路径上的结点

    参考资料

    算法学习记录-图——应用之关键路径(Critical Path)

    AOV网络与拓扑(一)

    展开全文
  • 图5——AOV网和AOE网

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

    AOV网:
    在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的网,简称AOV网。

    特点:
    1.AOV网中的弧表示活动之间存在的某种制约关系。
    2.AOV网中不能出现回路 。

    拓扑序列:

    设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1, v2, …, vn称为一个拓扑序列;
    当且仅当满足下列条件:若从顶点vi到vj有一条路径,则在顶点的拓扑序列中顶点vi必在顶点vj之前。

    拓扑排序:

    对一个有向图构造拓扑序列的过程称为拓扑排序 。
    在这里插入图片描述
    基本步骤:
    ⑴ 从AOV网中选择一个没有前驱的顶点并且输出;
    ⑵ 从AOV网中删去该顶点,并且删去所有以该顶点为尾的弧;
    ⑶ 重复上述两步,直到全部顶点都被输出,或AOV网中不存在没有前驱的顶点。

    —看上述步骤是不是觉得有点啰嗦,简单点操作:就是依次删除入度为0的结点。

    设计数据结构部分:

    在这里插入图片描述
    在这里插入图片描述

    基本思路:

    (1)找G中无前驱的顶点
    - 查找indegree [i]为零的顶点vi;
    (2)修改邻接于顶点i的顶点的入度(删除以i为起点的所有弧)

    • 对链在顶点i后面的所有邻接顶点k,将对应的indegree[k] 减1。
      为了避免重复检测入度为零的顶点,可以再设置一个辅助栈,若某一顶点的入度减为0,则将它入栈。每当输出某一入度为0的顶点时,便将它从栈中删除。
    void TOpSort(){
       int  top=-1, count=0;
       for(int i=0;i<vertexnum;i++)
           if(adjlist[i].in==0) 
                s[++top]=i;
             while(top!=-1){
                 j=s[top--];
                 cout <<adjlist[j].vertext;
                 count++;
                 p=adjlist[j].firstedge;
             while(p!=NULL){
                 k=p->adjvex;
                 adjlist[k].in--;
                 if(adjlist[k].in==0) 
                    s[top++]=k;
                 p=p->next;
             } 
         }
            if (count<vertexNum)
              cout<<“有回路”;
    }
    

    AOE网

    在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,边上的权值表示活动的持续时间,称这样的有向图叫做边表示活动的网,简称AOE网。
    需要注意的是,AOE网中没有入边的顶点称为始点(或源点),没有出边的顶点称为终点(或汇点)。

    性质:
    ⑴ 只有在某顶点所代表的事件发生后,从该顶点出发的各活动才能开始;
    ⑵ 只有在进入某顶点的各活动都结束,该顶点所代表的事件才能发生。

    存储结构的选择:

    为处理方便,同时采用了邻接矩阵边集数组两种存储结构。
    邻接矩阵可以方便的查找邻接点,完成时间的最早和最晚发生时间的计算。
    边集数组可以方便的计算时间的活动的最晚发生时间

    struct Edge{
    	int from;
    	int to;
    	int e;
    	int l;
    };
    
    class Grap{
    	int vertexnum,e;
    	int **adjlist;   //邻接矩阵
    	int start,end;
    	Edge *edge;  //边集数组
    public:
    	Grap(int n,int e);
    	int  path();
    };
    

    在这里插入图片描述

     q.push(0);//源点事件入队
    for(j=0;j<vertexnum;j++)	{  //初始化每个事件最早发生时间
    	ve[j]=0;	visit[j]=0;	}
    visit[0]=1;	
     while(!q.empty())	{		
    	i=q.front();       //利用标准模板库中的队列实现
    	q.pop();
    	for(j=0;j<vertexnum;j++){//计算i的邻接点的ve
    		if(adjlist[i][j]!=9999 && ve[i]+adjlist[i][j]>ve[j] ){
    			ve[j]=ve[i]+adjlist[i][j];
    			if(!visit[j])   //如果j没有被访问过,顶点j入队
    				q.push(j);
    			visit[j]=1;
    		}
    	}
    }
    

    在这里插入图片描述

      q.push(vertexnum-1);
    	for(j=0;j<vertexnum;j++)	{
    		vl[j]=ve[vertexnum-1];	visit[j]=0;	}
        while(!q.empty())	{
    		i=q.front();
    		q.pop();
    		for(j=0;j<vertexnum;j++)	{
    			if(adjlist[j][i]!=9999 && vl[i]-adjlist[j][i]<vl[j] ){
    				vl[j]=vl[i]-adjlist[j][i];
    				if(!visit[j])
    					q.push(j);
    				visit[j]=1;
    			}
    		}
    	}
    

    在这里插入图片描述

    for(i=0;i<e;i++)
    	{
    		edge[i].e=ve[edge[i].from];
    	}
    

    在这里插入图片描述

    for(i=0;i<e;i++)
    	{
    		edge[i].e=ve[edge[i].from];
    		edge[i].l=vl[edge[i].to]-adjlist[edge[i].from][edge[i].to];
    	}
    

    图的连通性

    一.无向图:

    要想判定一个无向图是否为连通图,或有几个连通分量,通过对无向图遍历即可得到结果。

    **连通图:**仅需从图中任一顶点出发,进行深度优先搜索(或广度优先搜索),便可访问到图中所有顶点。
    **非连通图:**需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

    求无向图的连通分量(非连通图的遍历方法)

    1.count=0;
    2.  for (图中每个顶点v)
           2.1 if (v尚未被访问过) 
                 2.1.1 count++;
                 2.1.2 从v出发遍历该图(函数调用);
    3.  if (count==1) cout<<"图是连通的";
         else cout<<"图中有"<<count<<"个连通分量";
    

    有向图的连通子图的求解过程

    ⑴ 从某顶点出发进完(即出栈)的顺序将顶点排列起来行深度优先遍历,并按其所有邻接点都访问。
    ⑵ 从最后完成访问的顶点出发,沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点,则从余下的顶点中最后访问的那个顶点出发,继续作逆向的深度优先遍历,直至有向图中所有顶点都被访问到为止。
    在这里插入图片描述

    展开全文
  • 数据结构:图:AOV网和AOE网

    千次阅读 2019-06-12 16:26:17
    AOV网(顶点表示活动的):以有向图中的顶点来表示活动,以有向边来表示活动之间的先后次序关系。...AOE网(边表示活动的):即顶点表示事件,有向边表示活动,有向边上的权值表示活动持续的时间。 AOV网...

    AOV网(顶点表示活动的网):以有向图中的顶点来表示活动,以有向边来表示活动之间的先后次序关系。

    AOV网的拓扑序列:AOV网的拓扑序列就是将AOV网中的所有顶点排成一个线性序列;拓扑序列实际上就是要由某个集合上的一个偏序关系得到集合上的一个全序关系(不同的算法可以得到不同的拓扑序列)。

    AOE网(边表示活动的网):即顶点表示事件,有向边表示活动,有向边上的权值表示活动持续的时间。

    AOV网和AOE网对比:

    1、AOV网的有向边不考虑权值,而AOE网的有向边考虑权值。

    2、AOV网入度为0的点可以有多个,而AOE网入度为0的点只能有一个(源点),AOV网出度为0的点可以有多个,而AOE网出度为0的点只能有一个(汇点)。                                                                                                                                                     

    3、AOV网和AOE网都不允许有环路。

    AOE网具有以下性质:

    1、只有在进入某一顶点的各条有向边代表的活动结束后,该顶点所代表的事件才能发生。                                                           

    2、只有在某个顶点代表的事件发生后,从顶点触发的各条有向边所代表的活动才能开始。                                                           

    3、在一个AOE网中,有一个入度为0的事件,称为源点,它表示整个工程的开始。同时有一个出度为0的事件,称为汇点,它表示整个工程的结束。

    对于AOE网,需要研究的问题是:

    1、完成整个工程需要多少时间?                                                                                                                                                     

    2、哪些活动是影响工程进度的关键?

    路径长度:AOE网的一条路径上所有活动的总和称为该路径的长度。

    关键路径:在AOE网中,从源点到汇点的所有路径中,具有最大路径长度的路径称为关键路径。

    关键活动:关键路径上的活动称为关键活动。

    显然,完成整个工程的最短时间就是AOE网中关键路径的长度,也就是AOE网中各关键活动所持续时间的总和。

    活动的持续时间dut(<j,k>):对于有向边<j,k>代表的活动,dut(<j,k>)是该有向边<j,k>的权值。

    事件可能的最早开始时间ve(k):对于顶点代表的事件,ve(k)是从源点到该顶点的最大路径长度。

    事件允许的最晚运行时间vl(k):对于顶点vk代表的事件,vl(k)是在保证按时完成整个工程的前提下,该事件最晚必须发生的时间。

    活动可能的最早开始时间e(i):假如活动ai代表的是有向边<j,k>,即ai是关联事件j和事件k的活动,则e(i) = ve(j)。

    活动允许的最晚开始时间l(i):假如活动ai代表的是有向边<j,k>,即ai是关联事件j和事件k的活动,则l(i) = vl(k) - dut(<j,k>)。

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

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

    2019-09-10 21:02:16
    AOV网 我们把施工过程、生产流程、软件开发、教学安排等都当成一个项目工程来对待,所有的工程都可以分为若干个“活动”的子工程。有很多场景对顺序有严格的要求,比如说建造一栋大楼必须先找好施工人员,购买各种...
  • AOV网和AOE网对比

    2013-06-25 04:27:00
    AOV网和AOE网对比 转载于:https://www.cnblogs.com/LoveFishC/p/3846907.html
  • 3.一般而言,AOV网(AOE网)只有一个源点一个汇点,即便存在多个源点或汇点,也可以通过添加超级源点超级 汇点来将它变成只含有一个源点一个汇点的AOV网AOE网) 4.AOV转换为AOE: (1)将AOV的每个顶点都拆...
  • 在网图中,最短路径是两顶点之间经历上权值之最短的路径。 Dijkstra算法: 求v到G中其余各顶点之间的最短路径。 设置一个集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v, 对vi∈V-S,假设从源点v...
  • AOV和AOE之间的区别联系

    千次阅读 2019-06-06 09:40:59
    定义:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的,我们成为AOV网(Activity On Vertex Network),AOV网中的弧表示活动之间的某种约束关系。AOV网中不...
  • AOV网AOE网的关系 AOV网(Activity On Vertex Network) 一项大的工程常被分为多个小的子工程, 子工程之间可能存在一定的先后顺序,即某些子工程必须在其他的一些子工程完成后才能开始; 在现代化管理中,人们...
  • AOVAOE网络

    2019-12-01 21:56:03
    AOV的概念: 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这样的有向图为顶点表示活动的,简称AOV网 2.拓扑排序:按照有向图给出的次序关系,将图中的顶点排成一个线性序列,对于...
  • 拓扑排序与关键路径(AOV网和AOE网)

    千次阅读 2018-08-07 17:47:20
    一、AOV网(Activity On Vertex Network) 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的,称为AOV网。 不能存在回路。 拓扑序列 设G(V,E)是一个...
  • AOV和AOE概念

    千次阅读 2017-09-21 09:57:19
    1、AOV网 定义:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的,我们成为AOV网(Activity On Vertex Network),AOV网中的弧表示活动之间的某种约束关系...
  • 有向无环图:AOV网AOE网

    千次阅读 2017-05-03 10:58:22
    DAG有着广泛应用,AOE网和AOV网都是DAG的典型应用。AOV网(Activity On Vertex NetWork)用顶点表示活动,边表示活动(顶点)发生的先后关系。 若中所有活动均可以排出先后顺序(任两个活动之间均确定先后顺序)...
  • 数据结构关于AOVAOE网的区别

    千次阅读 2016-07-11 17:08:42
    AOV网,顶点表示活动,弧表示活动间的优先关系的有向图。  即如果a->b,那么a是b的先决条件。 AOE网,边表示活动,是一个带权的有向无环图,  其中顶点表示事件,弧表示活动,权表示活动持续时间。 按...

空空如也

空空如也

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

aov网和aoe网